[BOJ/python]1092번 배

백준 1092번 파이썬 

문제 링크 - https://www.acmicpc.net/problem/1092

1092번: 배

그리디 알고리즘은 간단하다고 생각하고 최근에 많이 풀지 않았는데 까다로운 문제가 많았다. 처음에는 배와 크레인의 무게를 오름차순으로 정렬하여 그리디하게 할당했는데 반례가 있었다.

내림차순으로 정렬해야겠다는 구상을 했지만 코드로 구현하는 것도 쉽지는 않았다.

1-1. 풀이

박스 1개를 배치할 때 count를 1 늘려준다. count가 박스의 개수와 같을 때 전체 루프를 종료하고 답을 출력한다. 가장 무거운 박스의 무게가 크레인의 옮길 수 있는 최대 무게보다 크면 루프를 실행하지 않고 바로 -1을 출력한다.

• 크레인과 박스가 1대1로 대응되어야 하므로 이중 반복문을 사용한다.
• 하나의 크레인이 아직 옮기지 않는 박스를 찾는다. 박스를 옮기면 count를 1늘려주고, visited 배열에 표시한다.
• 모든 크레인을 한 번 다 탐색하면 시간을 1 늘려주고 다시 처음 크레인부터 탐색을 시작한다.

해당 코드로 문제를 풀게 되면 가장 무거운 크레인만 박스를 옮길 수 있는 최악의 경우에 O(NMM)의 시간 복잡도가 소요된다.

1-2. 코드

#배 greedy
N = int(input())
C= list(map(int, input().split()))

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

C.sort(key=lambda x:-x)
B.sort(key=lambda x:-x)

sol=0
count=0
visited=[0 for _ in range(M)]
if B[0] > C[0]:
    print(-1)
else:
    while count<M:

        for crain in range(N):              
            
            for box in range(len(B)): 
                        
                if not visited[box] and B[box] <= C[crain] :
                    
                    count+=1
                    visited[box]=1
                    
                    break
        sol+=1
        
    print(sol)

2-1. 시간 복잡도 최적화하기

박스는 내림차순으로 정렬되어 있다. 이 때 만약 c1크레인이 b1박스를 옮기고 c2 크레인이 b2박스를 옮기지 못하고 b3 박스를 옮겨야 한다면 1분 뒤에 c1 크레인이 b2 박스를 옮기면 된다.

책갈피를 하는 장치가 있다면 1분 뒤 상황에서 c1크레인은 위의 풀이처럼 처음 박스부터 탐색하지 않고 b2번 박스부터 탐색할 수 있을 것이다.

2-2. 최적화 풀이

positions 배열을 크레인의 개수만큼 만든다. postions[i] = v에서 i번 인덱스의 크레인은 v번 박스부터 탐색하면 됨을 의미한다.

• 책갈피가 마지막 박스의 인덱스에 올 때까지 반복문을 실행한다.
• 만약 i번 크레인에서 v번 박스가 방문되지 않았다면 count를 1 늘려주고 방문 표시를 한다.
• 방문 표시를 한 박스의 다음 인덱스를 책갈피에 저장하고 i번 크레인이 옮길 박스를 찾는 반복문을 종료한다.
• 방문된 박스라면 해당 크레인은 다음 박스를 탐색한다는 의미에서 postions[i]+=1을 해준다.
• positions[i]를 늘려가며 마지막 박스까지 탐색한다.
• 모든 박스가 옮겨질 때까지 위의 과정을 반복하면 된다.

2-3. 최적화 코드

N = int(input())
C = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))

C.sort(key=lambda x:-x)
B.sort(key=lambda x:-x)

sol = 0 # 시간
visited = [0 for _ in range(M)] 
count = 0 # 옮긴 박스의 개수 

positions = [0] * n

if B[0] > C[0]:
    print(-1)
else:
    while count < len(B):
        for i in range(N): 
            while positions[i] < len(B):
                if not visited[positions[i]] and C[i] >= B[positions[i]]:
                    visited[positions[i]] = 1
                    positions[i] += 1
                    count += 1
                    break
                positions[i] += 1
        sol += 1
    print(sol)