백준 1092 배 / python

문제 : 1092

풀이 point

$(N*N)$ 시간 복잡도가 들어가는 순간 시간초과이기 때문에 탐색 범위를 조금씩 줄여가면서 $(N*N)$을 만들지 않는 것이 가장 중요하다.

박스 무게와 크레인이 움직일 수 있는 무게 배열을 내림차순으로 정렬한다.

ex)
9 8 6 - crane
7 5 4 2 2 - box

crane을 기준으로 box를 들 수 있는지 판단한다. 만약 가장 큰 무게를 들 수 있는 크레인이 box를 들 수 없다면 그 이후 크레인은 그 박스를 절대 들 수 없다. (내림차순이기 때문)
그리고 1분이 지난 후 또 박스를 들어야할 때 크레인은 본인이 든 박스 이후 시점부터 탐색을 시작한다.(그 이전은 이미 끝난 것이기 때문에 볼 필요가 없음)

두 과정을 통해 시간을 줄여서 시간초과를 피할 수 있다.

풀이 방법

visit = [False]*M
pos = [0]*N

visit 배열(박스가 이미 옮겨졌는지 아닌지)과 pos(해당 인덱스의 크레인이 탐색 시작해야할 박스 위치)를 통해 위에서 말한 시간을 줄이기 위한 방법을 실행할 수 있다.

이때 visit배열을 활용하지 않고 remove를 쓸 수 있으나 뒤에 있는 값들을 앞으로 당겨오는 비용이 발생하기 때문에(최악의 경우 O(N)) visit배열을 썼다.
(사실 큰 차이는 없을 것이다. visit은 아예 걸러지지 못하고 무조건 봐야하는 단점이 있다.)

crane을 기준으로 박스를 옮길 수 있나 없나를 판단하여 모든 박스가 옮겨지는 순간 몇 분이 흘렀는지를 출력한다. 참고로 모든 박스를 옮길 수 없을 때는 -1을 출력하라 했기 때문에 가장 큰 crane이 가장 무게가 많이 나가는 box를 옮기지 못할 때 -1 출력 로직을 추가해야한다.

풀이 코드

N = int(input())
crane = list(map(int, input().split()))

M = int(input())
box = list(map(int, input().split()))

crane.sort(reverse=True)
box.sort(reverse=True)

visit = [False]*M
pos = [0]*N


if crane[0] < box[0]:
  print(-1)
  exit()

m = 0 # 옮겨진 박스 개수
done = 0

while done < M:
  for i in range(N):
    for j in range(pos[i], M):
      pos[i] = j + 1
      if visit[j]:
        continue
      if crane[i] >= box[j]:
        visit[j] = True
        pos[i] = j+1
        done += 1
        break
        
  m += 1

print(m)