문제
N팀 중 일부 팀의 카약이 부서졌고, 일부 팀은 여분 카약이 있다. 부서진 팀은 바로 옆(번호 ±1) 팀에서 여분을 빌릴 수 있을 때, 출발하지 못하는 팀 수를 최소화하라.
입력
첫째 줄에 N, 부서진 팀 수 S, 여분 팀 수 R, 이후 부서진 팀 번호와 여분 팀 번호가 주어진다.
출력
출발하지 못하는 팀의 최소 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 2 3 2 4 1 3 5 | 0 |
풀이
부서진 팀과 여분 팀이 겹치면 먼저 자기 카약을 수리하고, 나머지는 그리디하게 인접 팀에서 빌린다.
- 부서진 팀과 여분 팀의 교집합을 구해 자기 수리를 먼저 처리한다
- 남은 부서진 팀을 오름차순 정렬하여 순회한다
- 왼쪽 인접 팀(t-1)에 여분이 있으면 빌리고, 없으면 오른쪽(t+1)에서 빌린다
- 빌리지 못한 팀 수가 답이다
핵심 아이디어: 부서진 팀을 정렬하여 왼쪽 우선으로 빌리면 그리디가 성립한다.
코드
N, S, R = map(int, input().split())
team_a = set(map(int, input().split()))
team_b = set(map(int, input().split()))
ans = 0
diff = team_a & team_b
team_a = list(team_a - diff)
team_b = list(team_b - diff)
if not team_a:
ans = 0
else:
team_a.sort()
for t in team_a:
if t - 1 in team_b:
team_b.remove(t - 1)
elif t + 1 in team_b:
team_b.remove(t + 1)
else:
ans += 1
print(ans)복잡도
- 시간: O(S * R)
- 공간: O(S + R)