[백준] 1715 카드 정렬하기

백준 1715번 카드 정렬하기

자료구조 / 그리디 / 우선순위 큐

 

 

[문제]

 

이 문제는 어떻게 해야 '최소한의 비교'가 되는지를 먼저 볼 필요가 있다.

 

큰수 + 큰수 = 비교횟수가 큼

작은수 + 작은수 = 비교횟수가 작음

우리가 구하는 것 -> 최소한의 비교가 되는 경우

 

즉, 모든 데이터중에서 가장 작은 두개를 더하고 정렬후에 또 두개를 더하는 식으로 진행하면 된다.

 

그럴려면 데이터를 두개를 더하고 더한값을 리스트에 넣어주고 정렬해주는 방법을 여러번 진행하게 된다.

여기에서 반복문안에 sort()를 사용할 경우 시간초과가 발생한다.

 

그렇기에 자동적으로 정렬된 상태를 유지해주는 '우선순위 큐'가 필요하다:)

 

 

 

 

[과정]

 

1. 우선순위 큐 초기화

    1-1) 우선순위 큐에 숫자 데이터(input 값) 넣기

 

2. n-1번만큼 반복 (3개의 데이터가 있다면 2번의 덧셈이 필요하기 때문)

    2-1) 만약 큐가 비어있으면 break

    2-2) 큐에서 값을 두개 뽑아서 cnt변수에 저장

    2-3) result변수에 더해진 값을 더함

    2-4) 큐에 더해진 값을 넣음

 

3. result(결과) 출력

 

 

 

[우선순위 큐 사용법]

 

Priority Queue = 들어간 순서에 상관없이 데이터의 크기에 따라 정렬됨

q.put() : 데이터를 넣음

q.get() : 가장 작은 데이터를 출력 후 큐에서 삭제함

 

 

 

[소스코드]

 

# 카드 정렬하기

import sys
input = sys.stdin.readline
import queue

n = int(input())
q = queue.PriorityQueue()

for i in range(n):
    tmp = int(input())
    q.put(tmp)

result = 0
for i in range(n-1):

    if q == '':
        break
    else:
        cnt = q.get() + q.get()
        result += cnt
        q.put(cnt)
print(result)

 

 

---

 

 

 

[통과]

 

 

처음에는 리스트를 사용해서 sort()하고 del을 써서 시간초과가 나왔다.

'우선순위 큐'를 쓰니 import sys가 없어도 통과가 된다.

 

 

// 기존의 백준 아이디였던 ruky는 해당 이메일을 삭제한 관계로 더이상 못쓰게 되었다...

슬프다..

이제 이 닉네임을 잘 가꿔보자 ㅎㅎ

 

매일 11시에 하나씩 푸는데 꾸준히 되고 있어서 좋음 ㅎ