백준 1092번
https://www.acmicpc.net/problem/1092

문제

후기

⏰ 풀이시간 6시간 ++⏰

시간 초과, Value Error, Index Error, 틀렸습니다

모든 오답을 다 겪은 문제였다.

어떠한 박스도 들 수 없는 크레인은 쓸모 없기 때문에 일단 제거하고,

크레인을 가장 큰 순서부터 정렬한 후, 박스의 list 안에서 들 수 있는

가장 무거운 박스부터 들 수 있게 알고리즘을 구현했다.

해당 박스를 들고나면 박스를 pop 하고, 다음 크레인으로 넘어가며,

다음 크레인이 들 수 있는 박스가 없으면, 그 크레인은 pop 한다.

크레인을 1바퀴 다 쓰면 time 값을 1 증가시키는 식으로 구현하였고

예제 입력과 출력 모두 나의 답과 일치했다. 그리하여 정답이라 생각하고 제출하였다.

하지만 크레인과 박스의 무게를 계속 비교하고 값을 저장하는 과정에서 시간 초과가 발생한 것 같았다.

경험상 시간초과가 발생하는 경우는 웬만하면 접근 방식 자체가 잘못 된 것이었다.



코드를 여러 번 수정하였지만 해결하지 못했고, 아예 전부 지운 후 처음부터 코드를 짰다.

일일이 비교하면서 박스를 제거하는 것이 아니라,

for문 안에서 가장 무거운 박스부터 크레인의 무게와 비교하여

들 수 있으면 들면 되는것이었다. 그리고 그 박스를 제거하고, 다음 크레인으로 넘어간다.

풀고 나니 허무했지만, 오랜 시행 착오로 다음부터는 이런 문제가 나오면 최대한 쉽게 접근하는

방향을 먼저 떠올릴 수 있는 계기를 얻은 것 같다..

나의 잘못된 풀이

import sys

input = sys.stdin.readline

box = []

n= int(input())

crain = sorted(list(map(int,input().split())))

m= int(input())

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

crain.reverse()
box.reverse()


k= min(box)
remove_list = []

for i in crain:

    if i<k:

        remove_list.append(i)

for i in remove_list:

    if i in crain:

        crain.remove(i)

#어떠한 박스도 들수없는 크레인은 일단 제거하고 시작한다.



#앞에서 부터 1개씩 비교해 가면서 회전한다
#crain의 길이만큼 다 돌면 pass 하면서 box를 cnt만큼 pop한다. 
#crain의 길이를 다 돌기 전에 해당 list가 막히면 crain을 인덱스 값만큼 pop한다.  다시 반복시작 
time = 0
cnt = 0

while True:


    max_box = 0
    new_max_box = 0

    for i in range(len(crain)):

        error = 0  #크레인 체크용 

        for j in box: #박스안에서 

            if j<= crain[i]:  #크레인이 해당 박스보다 크다면 

                max_box=j  #이 박스는 해당 크레인으로 들수있습니다. 

                error +=1 #이 크레인은 쓸모있습니다. 
            
            if max_box>new_max_box:  # 들수있는 박스중 가장 큰 박스를 저장하기 위함 

                new_max_box = max_box

        if error ==0:  #크레인이 쓸모없으면  

            crain.pop(i) #제거합니다. 
            
        box.remove(new_max_box) #1루틴을 돌고 crain[i]로 들수있는 가장 무거운 박스가 제거됨 

        if len(box)==0:   #더이상 옮길 박스가 없으면 

            print(time+1)  #출력하고 종료하는데, 진행중인 상황에서 종료되었기 때문에 시간은 1 증가해서 출력 
            exit()        

        max_box=0
        new_max_box = 0

        cnt +=1 #크레인을 1개 사용했습니다. 

        if cnt == len(crain):  #크레인을 한바퀴 다 사용했다면 

            time +=1 # 소요시간 1 증가 

            cnt = 0 #크레인 사용횟수 초기화

나의 풀이

import sys

input = sys.stdin.readline

box = []

n= int(input())

crain = sorted(list(map(int,input().split())))

m= int(input())

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

crain.reverse()
box.reverse()

if box[0] > crain[0]:  #들수있는게 없으면 -1출력후 종료 
    print(-1)
    exit()

time = 0

while len(box) > 0: #박스가 전부 옮겨질때까지 

    time += 1

    # 크레인을 돌면서 박스를 옮긴다. 
    for i in crain:

        for j in range(len(box)):

            if i >= box[j]: #옮길수 있다면 

                del box[j]  #그 박스를 지운다. 

                break # 그 다음 crain으로 돌아간다. 

print(time)