[백준] 1175 카드 정렬하기 (Python)

[백준] 1175 카드 정렬하기 (Python)

 

Source

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

Code

import sys
from collections import deque
from bisect import bisect_left

input = sys.stdin.readline

n = int(input())
cards = [int(input()) for i in range(n)]
cards.sort()
cards = deque(cards)

ans = 0

if len(cards) == 1:
    print(0)

else:
    while len(cards) > 1:

        temp = cards.popleft() + cards.popleft()
        ans += temp
        cards.insert(bisect_left(cards, temp), temp)

    print(ans)

 

How to solve?

1. 리스트 sort()를 이용해 정렬한 뒤 deque로 자료구조를 변환해준다.

0번째 인덱스 부분에서 계속 pop()하여 값을 구할 것이기 때문에 deque로 O(1)만에 값을 리턴해주는 popleft()를 사용하기 위해 deque로 자료구조를 변환한다.

 

2. 만약 cards의 길이가 1이라면 답은 0이기 때문에 0 리턴.

 

3. 그게 아니라면 while문으로 들어가 popleft()두번 사용한 임시값을 구하여 정답에 더해주고 이분탐색으로 왼쪽에서부터의 인덱스 값을 구해 다시 더한 값을 넣어준다.

 

4. 만약 cards의 길이가 1이 되었다면 ans 출력.

 

One step more

해당 문제같이 자료구조에 계속해서 새로운 값이 순서대로 들어가야 하는 경우 heapq를 이용하여

heapq.heappush(heap, item) 함수를 사용하는 것이 효율적이다.