python 백준1715 카드 정렬하기(BOJ1715)

문제링크 : https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

처음에 문제읽고 그냥 차례대로 쭈르륵 더하면 되는거아냐? 너무 쉬운데? 했다가~

바로 틀려버리기

뭐지?? 하고 한두개 테스트 해봤더니 정말 답이 틀리게나온다!

그래서 규칙이 뭘까하고 한~~~참 고민하면서 적어보고 해서 겨우 해결했다..

해결 아이디어는! 간단한데 글로 적으려니깐 쉽지않네..가장 요긴하게 쓴건 우선순위 큐!

입력으로 받은 카드들을 큐에 담고

앞에 두개 꺼내서 더한걸 다시 큐에담고, 다음 두개 꺼내서 더해서 다시 큐에 담고

그리고 더하면서 큐에 담을때 그걸 출력할 결과값에 더해주기도 했다

그래서 큐가 빌때까지 하면! 끗

그렇게 해서 처음 제출한 코드

#우선순위 큐
import heapq

#입력 카드갯수
n = int(input())

q = []
for _ in range(n):
  heapq.heappush(q, int(input()))

#이전값 담아둘 변수
prev = 0
#결과값
result = 0
while q:
  #처음나온 값 저장
  if prev == 0:
    prev = heapq.heappop(q)
  else:
    #두번째 나오값을 더해서 큐에 추가하고 결과값에 더한다
    #그리고 prev값 초기화
    new = heapq.heappop(q)
    heapq.heappush(q, prev+new)
    result+= prev+new
    prev = 0
#출력
print(result)

그렇게 해서 맞긴했는데!

겁나 느리다

왜이렇게 느리지???

해서 봤더니 아마 가장 큰 문제는 입력시간이 아닐까 싶다

import sys

input = sys.stdin.readline

처음 제출했던 코드 그대로 위에 저 빠른 입력 코드만 추가했더니

낫밷

사실 시간은 채점서버의 환경에 따라 달라질수도 있겠지만 저렇게 큰 차이가 난다면 좀 기분이 안좋다...

그리고 저 코드에서 첫번째껄 prev에 저장하고 두번째껄 더한다음 다시 prev를 0으로 초기화 하는부분..

저부분을 좀 뭔가 느낌있게 바꿀수 있을것같은데..싶어서 다른사람들껄 보니 난 빠가였다

import heapq
import sys

input = sys.stdin.readline
n = int(input())

q = []
for _ in range(n):
  heapq.heappush(q, int(input()))
  
result = 0
while len(q) != 1 :
    prev = heapq.heappop(q)
    next = heapq.heappop(q)
    heapq.heappush(q, prev+next)
    result+= prev+next
print(result)

큐가 다 빌때까지하는게 아니라 마지막 하나 남을때까지 두개씩 뽑으면 되는거였다..

결국 마지막 2개는 모든수의 총합만큼 더하고 그걸 큐에 추가하기때문에 무시해도 된다

요정도에서 시마이

고인물들은 무슨 알파고가 짠것처럼 신기하고 빠르게 짠것도있는데 그정도까지는 원하지도않는다..