[1715] 카드 정렬하기 (python)

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

1715번: 카드 정렬하기

 

문제에 대한 접근법은 다음과 같이 접근하였다.

1. 주어진 카드 개수를 입력으로 받아 리스트 형식으로 저장한다

2. heapq를 이용하여 리스트 내 최소값을 구하기 쉽도록 만든다. (계산량 효율을 위해서 heapq를 쓴다)

3. 해당 리스트에서 heappop을 통해 가장 작은 2개의 값을 추출하여 first, second에 저장 후 둘을 더한 값을 결과값에 더한 뒤 원래 리스트에 heappush를 해준다.

4. 리스트의 N-1만큼 3번 문항을 반복 실행한다.

 

import sys
import heapq
from heapq import heappush, heappop, heapify #heapq 를 사용하기 위한 import

input = sys.stdin.readline

N = int(input()) # 카드 묶음의 개수
value = [int(input()) for _ in range(N)] # 묶음 카드의 개수

heapify(value)
#heapq로 정렬된 value값 확인 #O(n) 복잡도 : 인자로 넘기는 리스트의 원소수에 비례

result = 0
for i in range(0,N-1):
    result_first = heappop(value)
    result_second = heappop(value)
    next = result_first + result_second # 가장 낮은 2개의 cost 비교
    result += next
    heappush(value,next)
print(result)

 

위의 문제 접근 방식에 대해서 말했으니 문제를 풀면서 실수하였던 오답노트는 다음과 같다.

 

A. heapq에 대한 사용 여부

- 우선적으로 처음엔 quick sort를 사용할려고 하였다. 하지만 문제에서 제시된 N은 총 1,000,000까지가 최댓값이였으므로 NlogN을 보장한다하더라도 N * N log N 이 적용되어서 런타임에러가 나오는 문제가 발생하였다.

 

일반적으로 heapq module을 사용하게 된다면 O(n)으로 복잡도를 낮출 수 있다.

기존 인자를 가진 리스트를 heapq.heapify() 를 사용하여서 복잡도 부분에서 여타 다른 정렬보다 적은 복잡도를 보여 이점을 준 점을 생각하지 못하였다.

 

 

B. input() 함수와 sys.stdin.readline 과의 차이 구별

input 과 sys.stdin.readline은 같은 역할을 하지 않는다는 점이다.

 

input() 내장함수는 parameter로 prompt message를 받는다. 입력 전 prompt message를 출력해야하는 여건이 발생할 수 있어 약간의 계산이 더 들어갈 수 있다. sys.stdin.readline()은 prompt message를 인수로 받지는 않는다.

 

그리고 input() 함수는 입력 받은 문자를 삭제하고 return한다. 하지만 sys.stdin.readline은 개행 문자를 포함한 값을 리턴한다는 특징이 있다.

 

그러므로 prompt message를 출력, 개행 문자를 삭제한 값을 return하는 그 시간때문에 input이 더 느리는 것이 결론이다.

 

 

C. 입력 받을 조건의 분류

 

사소한 차이긴 하지만 이 문제를 풀기 전, 전 문제는 input을 list 형태로 한 행을 통해서 받아 입력을 받을 때 

list(map(int,input.split()))

위의 해당 처럼 받았었다.

하지만 문제에서 주어진 것은 한 열로 받기에 위의 코드와 같이 받아서 처리를 해야하거나 하나씩 받은 다음에 append를 써서 리스트 형태로 추가하는 방법으로 풀었어야 한다.