[Python] 백준 2751 (수 정렬하기2)

*문제에 대한 내 생각

 본 문제에 앞선 2750은 사실상 프로그래밍 예제에 불과할 정도로 쉬웠다.

 그러나 주어지는 수의 개수와 범위의 차이가 해당 문제의 난이도를 급상승시켰다.

 찾아보니 정렬알고리즘을 적용시켜 푼 사람들이 많았는데, 솔직히 무슨 말인지 모르겠음.

 (http://ejklike.github.io/2017/03/04/sorting-algorithms-with-python.html 가 그나마 설명을 잘 해놓았다.)

 애초에 이걸 파이썬으로 하니까 느려터졌...지...

 

 

*문제 풀이

-아이디어

 내가 처음 시도했던건 sort를 사용하는 것이었는데, 당연히 시간초과가 떴다. 아무래도 개수가 많다보니 

 정렬에 시간이 오래걸리는 듯 하다.

 그래서 든 생각은 전체 input의 리스트를 나눠서 정렬하는 것이었다.

 한번에 정렬하는 것이 오래걸린다면, 여러개로 나눠서 sort를 사용하면 가능할 것이라는 판단이었다.

 

-코드1

 주어지는 input이 짝수인지 홀수인지에 따라 리스트를 구별했다.

 예외처리를 한 이유는 리스트의 원소가 다 없어져 버리면 IndexError가 나와서 그렇다.

 

import sys

n = int(input())
odd = [] #홀수의 경우
notodd = [] #짝수의 경우

for i in range(n):
    sample = int(sys.stdin.readline())
    if sample%2 == 0:
        notodd.append(sample)
    else:
        odd.append(sample)

odd.sort(reverse=True) #내림차순
notodd.sort(reverse=True)

try:
    for i in range(n):
        if odd[-1] < notodd[-1]:
            print(odd.pop())
        else:
            print(notodd.pop())
except: #한 리스트가 비게되어 IndexError가 나는 경우
    if len(odd) == 0:
        for i in range(len(notodd)):
            print(notodd.pop())
    else:
        for i in range(len(odd)):
            print(odd.pop())

 

 

-코드2

 이후 생각난 방법으로, 홀수짝수가 아니라 주어질 input의 개수들을 반으로 나눠서 정리하는 방법이다.

 즉, n개가 주어지면 각 리스트에 n/2씩 집어넣어 sort를 사용한다. 

 결국 리스트에 넣는 정보들의 개수를 제외하고는 전부 같은 방식이다.

 

import sys

n = int(input())
sample1 = []
sample2 = []

for i in range(n):
    sample = int(sys.stdin.readline())
    if i%2 == 0: #i가 짝수인 경우
        sample1.append(sample)
    else:
        sample2.append(sample)

sample1.sort(reverse=True)
sample2.sort(reverse=True)

try:
    for i in range(n):
        if sample1[-1] < sample2[-1]:
            print(sample1.pop())
        else:
            print(sample2.pop())
except:
    if len(sample1) == 0:
        for i in range(len(sample2)):
            print(sample2.pop())
    else:
        for i in range(len(sample1)):
            print(sample1.pop())

 

 

*결과

 코드1의 경우 557바이트에 1924ms, 코드2는 591바이트에 1952ms가 나왔다.

 딱히 별 차이가 없어보인다.

 참고로 리스트를 3개이상으로 늘렸을때가 궁금했지만 코드로 구현을 못해서 시도를 못해봤다.

 (추가로 재미삼아 input을 랜덤으로 sample1과 sample2에 넣도록 해보니 3652ms가 나옴. 근데 이게 되네...)