Baekjoon #1715 - 카드 정렬하기

목차

1. 문제

2. 입출력 예시

3. 문제 풀이

1. 문제

• 백준알고리즘 문제 - 1715번 카드 정렬하기

2. 입출력 예시

입력 예시	출력 예시
3 10 20 40	100

3. 문제 풀이

이 문제는 시간관리에 있어서 애먹었던 문제이다. 문제를 해결하기 위한 논리는 매우 단순하다.

• 비교할 카드 묶음의 수량(n)을 입력받는다.
• 만약에 카드 묶음의 수량이 1개일 경우는 비교할 필요가 없으니 결과값을 0으로 출력하고, 그 외에는 결과값(total)을 0으로 초기화한 후 카드 묶음의 수량만큼 반복하여 카드 묶음의 크기를 입력받아 리스트(lst)에 추가한다.
• 비교를 할 때 카드 묶음의 크기가 작은 순으로 연산을 수행해야 최솟값이 나오므로, 리스트를 오름차순으로 정렬한다.
• while문을 통해 리스트의 크기가 1보다 클 때까지 반복하는 동안 리스트의 첫 번째 요소와 그 다음 요소를 리스트에서 추출(pop)하여 이 둘을 더한다. 이렇게 더한 값을 리스트의 첫 번째 요소로 삽입하고, 이 값을 결과값에 더한다. (아래 표 참조)
• 반복이 종료되면 결과값을 출력한다.

반복 횟수	리스트(전)	리스트(후)	결과값
0	[]	[10, 20, 40]	0
1	[10, 20, 40]	[30, 40]	30 (10 + 20)
2	[30, 40]	[70]	100 (30 + (30 + 40))

이를 리스트를 사용해서 구현하면 아래와 같다. 그러나 이 코드를 제출할 경우에는 시간초과라는 결과를 받게 된다.

import sys


n = int(input())

if n == 1:
    print(0)

else:
    total = 0

    lst = [int(sys.stdin.readline()) for _ in range(n)]
    lst.sort()

    while len(lst) > 1:
        tmp1 = lst.pop(0)
        tmp2 = lst.pop(0)
        lst.insert(0, tmp1 + tmp2)
        total += tmp1 + tmp2
    print(total)

이를 해결하기 위한 방법으로 큐(queue)를 생각해보았으나, 이는 FIFO(First-In First-Out) 즉, 먼저 들어온 데이터를 먼저 내보내는 형식이기 때문에 맨 앞에 요소를 추가할 수 없다. 따라서, 우선순위가 높은 데이터를 먼저 내보내는 우선순위 큐(Priority Queue)를 사용하여야 한다. 위 코드에서 구현한 방식이 바로 우선순위 큐의 작동 원리인 셈이다. 그렇다면 왜 리스트로 이를 구현했을 때에는 시간복잡도에 차이가 발생할까?

리스트에서 요소를 추가하고 이를 우선순위를 기준으로 정렬하였다고 해보자. 맨 앞에 위치한 요소는 우선순위가 가장 높은 요소이다. 이를 리스트에서 호출할 때 맨 앞에 위치한 인덱스(Index)를 사용하면 되므로 시간복잡도가 크지 않다. 그러나 리스트에 위치한 요소를 삭제할 때에는 해당 요소 뒤에 위치한 요소들의 인덱스를 전부 앞당겨주어야 한다. 이와 마찬가지로 리스트의 맨 앞에 요소를 추가할 때, 기존에 위치하던 요소의 인덱스를 전부 뒤로 밀어내야 한다. 만약 추가할 자료가 n개라고 가정했을 때 시간복잡도는 O(n)이 된다. 그러나 우선순위 큐는 힙(heap) 기반으로 되어 있으며, 데이터 삽입 및 삭제 시 시간복잡도는 O(log₂N)이다. 이에 대해서는 따로 자세히 포스팅하도록 할 예정이다.

우선순위 큐를 사용한 코드는 아래와 같으며, 메모리 31,672 KB, 시간 220 ms가 소요되었다.

import sys
import heapq


n = int(input())

if n == 1:
    print(0)

else:
    total = 0

    lst = [int(sys.stdin.readline()) for _ in range(n)]
    lst.sort()

    heapq.heapify(lst)

    while len(lst) > 1:
        tmp1 = heapq.heappop(lst)
        tmp2 = heapq.heappop(lst)
        heapq.heappush(lst, tmp1 + tmp2)
        total += tmp1 + tmp2
    print(total)