백준 1092 배 Python3

https://www.acmicpc.net/problem/1092

1092번: 배

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ1092.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

N = int(input())
crane = list(map(int, input().split()))
M = int(input())
box = list(map(int, input().split()))
if max(crane) < max(box): print(-1)
else:
    crane.sort(reverse = True)
    box.sort(reverse = True)
    time = 0
    b_visit = [0]*M
    c_pos = [0]*N
    cnt = 0
    while cnt < M:
        time += 1
        for c in range(N):
            while c_pos[c] < M:
                #박스 옮길 수 있는 경우,
                if not b_visit[c_pos[c]] and box[c_pos[c]] <= crane[c]:
                    b_visit[c_pos[c]] = 1
                    c_pos[c] += 1
                    cnt += 1
                    break
                c_pos[c] += 1
    print(time)

---

풀이 과정

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

#모든 박스를 옮길 수 없는 경우, -1 출력
#가장 무거운 박스가 가장 큰 무게제한을 가진 크레인보다 큰 경우, 박스를 옮길 수 없다
if max(crane) < max(box): print(-1)
else:
	#크레인의 무게제한과 박스의 무게를 내림차순으로 정렬 -> T(nlogn + mlogm)
    crane.sort(reverse = True)
    box.sort(reverse = True)
    
    #i번째 박스를 옮긴 경우 b_visit[i] = 1, 옮기지 않은 경우 b_visit[i] = 0
    b_visit = [0]*M
    
    #i번쨰 크레인이 옮길 박스를 찾기 위해 c_pos[i]번째 박스부터 탐색해야 한다
    #c_pos[i]-1까지의 박스는 i번째 크레인의 무게제한보다 크기 때문에 다시 탐색할 필요가 없다
    c_pos = [0]*N
    
    #옮긴 박스의 수
    cnt = 0
    time = 0
    
    #박스를 모두 옮길 때까지 반복
    while cnt < M:
        time += 1
        for c in range(N):
        	#c번째 크레인이 옮길 수 있는 박스가 있는지 더 탐색해야 하는 경우
            while c_pos[c] < M:
                #c_pos[c]번째 박스를 옮길 수 있는 경우
                if not b_visit[c_pos[c]] and box[c_pos[c]] <= crane[c]:
  					#박스를 옮긴다
                    b_visit[c_pos[c]] = 1
                    cnt += 1
                    #현재 시간에 모든 박스를 옮기지 못한 경우, 1초 후에 옮긴 박스의 다음 박스부터 탐색하기 위해 c_pos[c] 값을 1 증가시킨다
                    c_pos[c] += 1
                    #현재 시간에 크레인이 박스 하나를 옮겼으므로 break
                    break
                #c_pos[c]번째 박스를 옮길 수 없는 경우, 다음 박스를 탐색한다
                c_pos[c] += 1
    print(time)

시간복잡도를 생각해 보자.

박스의 개수 = 10,000, 크레인의 개수 = 50, 모든 박스의 크기 = 50, 크레인의 제한무게 = 50 - 1개, 1 - 49개인 경우를 생각해보자.

1. box, crane 정렬 -> T(MlogM + NlogN) = 10000*log(10000) + 50*log(50) = 약 40085

2. while 문

처음 1초는 크레인 제한무게가 50인 경우, 박스 하나를 바로 옮기므로 1번 연산이 필요하며, 나머지 각 크레인은 무게제한이 1이기 때문에 모든 박스를 옮기지 못하므로 10,000번 연산이 필요하다. 즉, 1+49*10,000번의 연산이 필요하다.2초부터 10,000초까지는 제한무게가 50인 크레인은 1번 연산이 필요하고, 나머지 49개의 크레인도 c_pos[i] = 10,000이기 때문에 1번의 연산이 필요하다. 즉, 2초부터 10,000초까지 총 50*9999번의 연산이 필요하다.따라서 총 연산 횟수는 40085 + 490,001 + 499,950 = 1030036번 정도이다.

---

오답 노트 

처음에는 크레인의 무게제한과 박스의 무게를 내림차순으로 정렬한 다음, 박스를 앞에서부터 차례대로 옮기는 방식으로 문제를 풀었다. 예제는 통과하였는데, 2%에서 틀렸습니다가 나왔다.

반례는 크레인의 무게제한 = 6, 8, 9, 박스무게 = 2, 4, 4, 5, 9, 9인 경우이다.

시간 1초에 크레인 무게제한-박스무게(크레인이 옮긴 박스)는 6-2, 8-4, 9-4이다. 

남은 박스의 무게 = 5, 9, 9

시간 2초에 크레인 무게제한-박스무게는 6-5, 9-9이다.

남은 박스의 무게 = 9

시간 3초에 크레인 무게제한-박스무게는 9-9로 3초의 시간에 다 옮길 수 있다.

 

하지만, 정답은 2초이다.

시간 1초에 크레인 무게제한-박스무게는 9-9, 8-5, 6-4, 남은 박스무게 - 9, 4, 2

시간 2초에 크레인 무게제한-박스무게는 9-9, 8-4, 6-2로 2초만에 다 옮길 수 있기 때문이다.

 

따라서, 오름차순으로 정렬하여 문제를 푸는 방식으로 문제를 해결할 수 없었다.

그렇다면 내림차순으로 정렬하여 문제를 풀어나가면 가장 무거운 박스부터 옮겨 나가면 된다.

옮길 수 있는 박스를 찾으면 list.pop(i)를 해나가며 문제를 풀면 정답은 맞지만 시간초과가 났다.

 

#틀린 코드
N = int(input())
crane = list(map(int, input().split()))
M = int(input())
box = sorted(list(map(int,  input().split())), reverse=True)
if max(crane) < box[0]: print(-1) 
else:
    crane.sort(reverse = True)
    time = 0
    while box:
        time+=1
        c = 0
        b = 0
        while c < N and box:
            if box[b] <= crane[c]:
                box.pop(b)
                c+=1
            else:
                b+=1
    print(time)

시간 복잡도를 계산해보니 다음과 같았다.

박스의 개수 = 10,000, 크레인의 개수 = 50, 모든 박스의 크기 = 크레인의 제한무게의 최댓값인 경우를 생각해보자.

1. box, crane 정렬 -> T(MlogM + NlogN) = 10000*log(10000) + 50*log(50) = 약 40085

2. while문 -> 10,000 * 50 * 10,000  =  10,000,000,000

1억 번의 연산에 1초 정도 소요되기 때문에 10초 이상이 걸린다.

따라서 시간초과가 발생한다.