Baekjoon 1715.py [카드 정렬하기]

hohooodo·2021년 7월 23일
0

Problem Solving

목록 보기
32/32
post-thumbnail

문제가 궁금하다면?

첫번째 풀이(시간초과)

import sys
import heapq

input = sys.stdin.readline

n = int(input())
cards = [int(input()) for _ in range(n)]
cnt = 0

while True:
    cards.sort(reverse = True)
    if n == 1:
        print(0)
        break
    if len(cards) == 2:
        print(sum(cards)+cnt)
        break

    v1 = cards.pop()
    v2 = cards.pop()
    cards.append(v1+v2)
    cnt += v1+v2

두번째 풀이(통과)

import sys
import heapq

input = sys.stdin.readline

n = int(input())
cards = [int(input()) for _ in range(n)]
cnt = 0
heapq.heapify(cards)

while True:
    if n == 1:
        print(0)
        break
    if len(cards) == 2:
        print(sum(cards)+cnt)
        break

    v1 = heapq.heappop(cards)
    v2 = heapq.heappop(cards)
    heapq.heappush(cards, v1+v2)
    cnt += v1+v2

풀이 복기

문제의 로직은 간단하다

  • 카드리스트에서 제일작은 수 2개 찾기
  • 찾은 수 더해서 카드리스트에 넣기
  • 카드 리스트가 하나가 될때까지 반복하기

첫번째 풀이에서는 카드 리스트에서 제일작은 수 찾는방법을 sort()를 사용했다. 이 방법을썼을때 시간초과나서 방법을 바꿨다.

사실 시간초과 나는건 당연했다. 카드리스트 최댓값은 100,000개 였는데 sort()를 사용할때마다 O(n)의 시간이 걸리므로 최대 100,000^2 번의 연산이 필요하게된다.
이 문제의 시간제한은 2초 즉, 약 40,000,000번의 연산이 최대이므로 불가능한 방법이였다.

두번째 풀이는 heap을 사용해 풀었다. 사실 첫번째 방법에서 바꾸는방법이 생각 안나서 알고리즘 분류를 보고 힌트를 얻었다.

heap자료구조는 아직 사용해본적이 없기때문에 추후에 공부할 예정임

profile
글을 잘쓰는 개발자가 되고싶습니다

0개의 댓글