[백준 1092번] 파이썬 - 배

문제 참고 (https://www.acmicpc.net/problem/1092

1092번: 배

그리디 문제에 맞게 접근 방법을 우선 찾게 되었고, 시간 초과의 문제를 해결하기 위해 많이 고민하였다.

 

처음 내가 푼 코드이다.

import sys
N = int(input())
weight_restric = (map(int, sys.stdin.readline().split()))
M = int(input())
weight = map(int, sys.stdin.readline().split())

# 모든 박스를 배로 옮기는데 드는 시간의 최솟값
# 오름 차순으로 정리하니 크레인 무게 = 1 2 3 4, 박스 무게 = 1 1 2 2 3 3 4 4 인경우 오류 발생하고 해결하려니 너무 길어진다.
# 2중 for문 써서 그런지 시간초과
# 박스의 무게, 크레인 무게제한 내림 차순 정리로 풀어준다.

weight = sorted(weight, reverse=True)
weight_restric = sorted(weight_restric, reverse=True)
for k in range(N-1, -1, -1):
    if weight_restric[k] < weight[-1]:
        weight_restric.remove(weight_restric[k])
    else:
        break

cnt = 0
if len(weight_restric)==0:
    print(-1)
else:
    while weight:

        # 무게 제한 큰 거부터 시작해서 옮길 수 있는 박스가 있다면 제거해준다.
        for i in weight_restric:
            
            for j in weight:
                if i >= j:
                    weight.remove(j)
                    break

        cnt+=1

    print(cnt)

우선, 무게 제한이 낮아 사용하지 못하는 크레인을 제거해주는 FOR문 1번

크레인을 순회하며 박스를 제거하는 FOR문 2번을 포함하여 총 3번의 FOR문을 써주었다.

 

여러 테스트 케이스를 만들어서 답을 구해보았고 정답이 잘 나왔지만 결과는 시간 초과..

오답 중에 시간 초과가 제일 힘든 것 같다. 다른 방법을 어떻게 구현할지 잘 모르기 때문인 것 같다.

 

구글의 도움을 받으며 시간을 줄일 수 있는 방법을 고민해보았다. 내가 생각하기엔 미리 크레인을 제거해주기 위한 반복문을 사용하지 않고 아래와 같이 if문을 이용해주었다.

for k in range(N-1, -1, -1):
    if weight_restric[k] < weight[-1]:
        weight_restric.remove(weight_restric[k])
    else:
        break

if weight and i < weight[-1]:
                continue

위의 경우 가장 가벼운 박스와 비교하여 먼저 제거 해주었고, 아래의 경우도 마찬가지의 원리로 옮기지 못하는 크레인은 바로 다음 크레인으로 넘겨주었다.

 

가장 큰 차이는 박스를 옮기는 과정에서, 남아있는 박스 중 자기가 옮길 수 없는 것이 없는 경우에서의 시간 단축 인 것같다.

혹시나 해서 처음 시간 초과 코드에 if 문을 넣어보았지만 마찬가지로 시간초과였다.

 

 

 

N = int(input())
weight_restric = (map(int, sys.stdin.readline().split()))
M = int(input())
weight = map(int, sys.stdin.readline().split())

# 모든 박스를 배로 옮기는데 드는 시간의 최솟값
# 오름 차순으로 정리하니 크레인 무게 = 1 2 3 4, 박스 무게 = 1 1 2 2 3 3 4 4 인경우 오류 발생하고 해결하려니 너무 길어진다.
# 2중 for문 써서 그런지 시간초과
# 박스의 무게, 크레인 무게제한 내림 차순 정리로 풀어준다.

weight = sorted(weight, reverse=True)
weight_restric = sorted(weight_restric, reverse=True)

cnt = 0
# 무게 제한이 가장 큰 크레인이 가장 무거운 박스를 못옮긴다면 -1 출력
if weight_restric[0] < weight[0]:
    print(-1)
else:
    while weight:

        # 무게 제한 큰 거부터 시작해서 옮길 수 있는 박스가 있다면 제거해준다.
        for i in weight_restric:
            # 시간을 줄여주기 위해서 박스를 옮기기 전 가장 가벼운 박스를 옮길 수 있는지 여부확인
            # 옮기지 못한다면 다음 크레인으로 바로 넘어가준다.
            if weight and i < weight[-1]:
                continue
            # 옮길 수 있는 박스를 옮긴 후 박스 리스트에서 제거
            for j in weight:
                if i >= j:
                    weight.remove(j)
                    break

        cnt+=1

    print(cnt)

브루트 포스를 풀며 2중 for문에 익숙해졌던 나에게 그리디 알고리즘은 조금은 힘들었다

힘든 만큼 많은 것을 배울 수 있었고 특히,

1. 사람이 보는 편리함과 컴퓨터가 느끼는 편리함은 다르다.
2. 문제를 풀기 전 접근 방법에 대한 많은 고민이 필요하다.

위 2가지에 대해 뼈저리게 느꼈다.