[백준] 2891번. 카약과 강풍

아이디어

• 프로그래머스에서 비슷한 문제여서 만만하게 봤는데 온갖 반례에 허덕였다.
• 포인트는 여분의 카약이 있는 팀이 부서졌을 때 자신의 것을 고쳐야 한다는 것!
• 카약을 빌려주는 순서가 있기때문에 정렬을 꼭 해줘야 한다.
• 주의 : remove()로 원소를 빼고 나면 index 순서가 내가 생각했던 것과 달라질 수 있음

시간 복잡도

• for문 + for문

코드

import sys
input = sys.stdin.readline

n, s, r = map(int, input().split())
s_list = list(map(int, input().split()))
r_list = list(map(int, input().split()))
k_list = [] # 자힐하고 남은 팀

# 자기 자신에게 여분의 카약을 쓸 때
for team in r_list:
	# 자힐이면 손상된 리스트에서 없애주고
    if team in s_list:
        s_list.remove(team)
    # 자기자신이 없으면 아직 빌려줄 수 있다(r_list를 remove하니까 원소가 뒤섞임 -> 그래서 새로운 list를 만들어줌)
    else:
        k_list.append(team)

# 남은 여분 카약으로 빌려주기(내림차순이니까 자신보다 큰애 먼저 빌려주기)
for team in k_list:
    if s_list == []:
        break
    elif team + 1 in s_list:
        s_list.remove(team + 1)
    elif team - 1 in s_list:
        s_list.remove(team - 1)
    
print(len(s_list))