백준 온라인 저지 2751번 수 정렬하기 2

문제 링크

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

풀이 전 계획과 생각

이 문제는 일단 문제가 무엇을 요구하는지 생각하는 데는 별도의 시간이 걸리지 않는 간단명료한 문제라고 할 수 있다.

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

백준에서 최근에 다른 쉬운 문제와 어려운 문제도 여럿 풀어 보았는데 쉬워 보이는데 '틀렸습니다'가 아닌 '시간 초과'가 뜨는 경우가 많았다. 그래서 이 문제의 함정도 아주 많은 양의 수를 입력했을 때 시간초과가 뜨지 않도록 시간복잡도에 신경써야 한다는 점이라고 생각했다.

일단 나보고 아무런 정보 없이 그냥 오름차순으로 정렬하는 코드를 외워서 써보라고 하면 제일 먼저 생각나는 건 가장 기본적인 선택정렬이다.

def sorter(arr):
    arr_output=[]
    
    for i in range(len(arr)):
        initial=arr[i]
        indexno=i
        for j in range(i,len(arr)):
            if initial>arr[j]:
                initial=arr[j]
                indexno=j
        if initial!=arr[i]:
            arr[i],arr[indexno] = arr[indexno],arr[i]
    return arr  

물론 여기에다가 첫째줄에 입력할 정수의 개수를 입력받고 다음 줄부터 정렬할 정수들을 입력받는 과정을 코드로 작성하라고 하면 예전 백준 문제에서 작성한 것과 비슷한 코드를 이렇게 작성하게 될 것이다.

counter=int(input(""))
table=[]
for i in range(counter):
    table.append(int(input("")))
output=sorter(table)
for unit in output:
    print(unit)

하지만 이 문제에는 이렇게 일반적으로 입력하면 '시간 초과'가 뜰 것이라는 함정이 있는 것 같아서 조금 더 조사해서 더욱 효율적인 합병 정렬을 해보기로 했다.

풀이 (코드 블록 첨부)

결론부터 말하자면 합격 처리된 코드는 이렇게 입력했다.
참고문헌
이관용·김진욱 (2018) 『알고리즘』 서울: 한국방송통신대학교출판문화원

참고도서에는 수도코드 형태로 대략적인 내용이 나오는데 물론 파이썬의 리스트는 다른 언어의 배열과 다르기 때문에 내용을 참고해서 합병정렬 함수를 구현해보았다.

# 2751 수 정렬하기 2
import math
import sys
def merger(arr_l, arr_r, l, m):
    i=0
    j=0    
    k=0
    arr_m = []
    while i<l and j<m:
        if arr_l[i]<=arr_r[j]:
            arr_m.append(arr_l[i])
            k+=1
            i+=1
        else:
            arr_m.append(arr_r[j])
            k+=1
            j+=1
    
    for x in range(i,l):
        arr_m.append(arr_l[x])
        k+=1
    for y in range(j,m):
        arr_m.append(arr_r[y])
        k+=1
    return arr_m
            
def mergeSort(arr,n):
    if n>1:
        mid=math.floor(n/2)
        arr_left = mergeSort(arr[:mid],mid)
        arr_right = mergeSort(arr[mid:],n-mid)
        
        arr = merger(arr_left,arr_right,mid,n-mid)
    return arr
   

counter=int(input(""))
table=[]
for i in range(counter):
    
    table.append(int(sys.stdin.readline()))
#print(table)
#print(mergeSort(table,len(table)))
output=mergeSort(table,len(table))
for unit in output:
    print(unit)

풀이하면서 막혔던 점과 고민

풀면서 가장 험난하게 막혔던 지점은 물론 이렇게 해도 처음에는 '시간 초과'가 떴다는 것이다.

백준에서 파이썬은 '시간 초과'가 더 많이 뜬다는 소문이 많았기 때문에 이게 파이썬에서 되긴 되는지 슬슬 걱정이 되어서 제출 현황을 검색해보았다.

참고로 저 위의 '맞았습니다' 세 개 중 두 개가 나다. ㅋㅋㅋ

한참을 페이지를 넘겨보니 간혹 '맞았습니다'가 있긴 있었다. 그래서 되긴 되는구나 하고 힌트라도 얻어보려고 구글에서 풀이 결과를 검색해보았더니 다들 그냥 파이썬 내장함수 sorted()를 쓰셨다.

그리고 문제가 하나 더 있었다. 문제를 처음부터 다시 읽어보자.

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

즉 입력값 자체가 최대 100만 개일 수가 있다. 그것을 입력하는 과정도 시간 초과가 될 수 있다.

그래서 복수의 입력값을 받는 과정도 이렇게 검색의 도움을 받아 최적화했다.

import sys
counter=int(input(""))
table=[]
for i in range(counter):
    
    table.append(int(sys.stdin.readline()))

결론적으로 입력을 input() 대신 sys.stdin.readline()으로 바꾸기만 했더니 간신히 합격이 되었다.

풀이 후 알게된 개념과 소감

입력값을 받는 데 의외의 복병이 있어서 나름 신경써서 수정했기 때문에 궁금해서 합격하신 다른 분들의 공개 코드도 모두 검색해 봤다. 대부분 sort()나 sorted() 쓰셨고 소수의 시간이 조금 더 많이 뜨는 분들은 나처럼 합병정렬을 하셨더라.
sys.stdin.readline()을 이번에 알게 되었으니 입력값을 받을 때 앞으로 계속 잘 활용해야겠다.