• 출처 : https://www.acmicpc.net/problem/1092

• 풀이

  1. 크레인 리스트, 박스 리스트 내림차순 정렬
  2. 모든 크레인에 대해 이동 가능한 무게의 박스 각각 저장
  3. 모든 크레인을 돌면서 이동 가능한 무게의 박스 중아직 이동하지 않은 박스 이동
  4. 3번을 모두 이동할 때까지 반복

• 소감

  • 혼자 시도했던 풀이가 시간 초과가 나서 검색해서 나온 풀이를 참고했다
  • 정답 풀이와 다른 점은
    • 나는 이동이 안 된 박스를 찾을 때 전체 박스에 대해 탐색을 했고
    • 정답은 가능한 무게의 박스만 탐색을 해서 그런 것 같다

틀린 코드

def init():

    n = int(input(''))
    crane_list = list(map(int, input('').split(' ')))
    m = int(input(''))
    box_list = list(map(int, input('').split(' ')))

    return n, m, crane_list, box_list


def get_box_idx(crane_idx, box_idx, box_excluded):

    while box_idx < m:

        if not box_excluded[box_idx]:
            if crane_list[crane_idx] >= box_list[box_idx]:
                return box_idx

        box_idx += 1

    return -1

def get_time():

    if max(crane_list) < max(box_list):
        return -1

    crane_list.sort(reverse=True)
    box_list.sort(reverse=True)

    crane_excluded = [False] * n
    box_excluded = [False] * m

    count = 0

    while True:

        crane_idx = 0
        box_idx = -1

        finished = False

        while crane_idx < n and box_idx < m:

            box_idx = get_box_idx(crane_idx, box_idx+1, box_excluded)
            if crane_idx == 0 and box_idx < 0:
                finished = True
                break

            box_excluded[box_idx] = True
            count += 1

            crane_idx += 1

        if finished:
            break
    
    return count


n, m, crane_list, box_list = init()

result = get_time()

print(result)

맞은 코드

def get_time():

    # 이동이 불가능할 경우
    if max(box_list) > max(crane_list):
        return -1

    # 내림차순으로 정렬
    crane_list.sort(reverse=True)
    box_list.sort(reverse=True)

    # 각 크레인 별 이동 가능 박스 저장
    crane_dict = dict()
    for i in range(n):
        for j in range(m):

            if crane_list[i] >= box_list[j]:
                if crane_list[i] not in crane_dict:
                    crane_dict[crane_list[i]] = []
                crane_dict[crane_list[i]].append(j)

    answer = 0
    move_count = 0
    moved = [False] * m

    # 모두 다 옮길 때까지 반복
    while move_count < m:

        answer += 1

        # 모든 크레인에 대해
        for i in range(n):
            if crane_list[i] in crane_dict:
                # 이동 가능한 박스 반복
                for j in crane_dict[crane_list[i]]:
                    if not moved[j]:
                        moved[j] = True
                        move_count += 1
                        break

    return answer


n = int(input(''))
crane_list = list(map(int, input('').split(' ')))
m = int(input(''))
box_list = list(map(int, input('').split(' ')))

result = get_time()

print(result)