글 읽기 - 두 알고리즘의 차이를 가르쳐 주세요 [병합정렬 매우 기본문제]

kani215 4년 전 0

왼쪽이 제꺼 오른쪽이 정답자의 코드입니다.

둘 다 제 컴퓨터에서는 잘만 작동되는데

제출을 해보면 효율이 제 것이 나쁜지 왼쪽 코드만 시간초과라고 뜨네요

# 제 코드 (시간초과의 코드)
import sys
T = int(sys.stdin.readline())
emplist =[]

for i in range(T) :
    test_case = int(sys.stdin.readline())
    emplist.append(test_case)
    
mid = len(emplist)//2
g1 = emplist[:mid]
g2 = emplist[mid:]
g1.sort()
g2.sort()
    
try :
    for i in range(T) :
        if g1[0] > g2[0] :
            print(g2.pop(0))
        else :
            print(g1.pop(0))
except : 
    if len(g1) == 0:
        for i in range(len(g2)):
            print(g2.pop(0))
    else:
        for i in range(len(g1)):
            print(g1.pop(0))
            
# 밑이 정답자의 코드
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())
            
            

djm03178 4년 전 0

list.pop(0)는 가장 앞의 원소를 빼낸 뒤 뒤의 모든 원소를 전부 한 칸씩 당겨오기 때문에 원소의 수에 비례하는 시간이 걸립니다.

jh05013 4년 전 1

그와 별개로 오른쪽의 코드는 바람직한 구현도 아닌 것 같습니다. 병합 정렬을 직접 구현한다면 .sort를 쓰지 않고 재귀 함수를 정의해야 의미가 있지 않을까요?

jh05013 4년 전 1

오른쪽의 코드 출처를 찾아봤는데 병합 정렬을 구현하려는 의도가 아니었군요. 해당 블로그 글에서 시간 초과가 난 이유는 정렬 문제가 아니라 sys.stdin.readline을 사용하지 않았기 때문입니다.

kani215 4년 전 0

두 분 조언 감사합니다. 정렬 문제를 풀이하니 끓어 오르네요 확 어려워졌습니다 ㅎㅎ

흥미진진하네요 pop에 그런 기능이 있는지 몰랐습니다. 좀더 도전해봐야겠습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

두 알고리즘의 차이를 가르쳐 주세요 [병합정렬 매우 기본문제]

kani215 4년 전 0

djm03178 4년 전 0

jh05013 4년 전 1

jh05013 4년 전 1

kani215 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말