글 읽기 - 파이썬 병합 정렬

bak9234 2년 전 0

여기서 어떻게 해야 연산 시간을 더 단축할 수 있는지 의문이 들어 질문 올립니다.

from sys import stdin

def Merge():
    global sizCntr
    global switch
    while True:
        # mrgArr의 0번과 1번 리스트의 역할을 바꿉니다. 초기에는 0번 리스트에서 정렬하여 1번 리스트에 기록합니다.
        switch = 1-switch
        for i in range(0,N,sizCntr*2):
            # 작업영역 내에서 각각 몇 번째 수를 비교해야 하는 지 나타내는 지역변수입니다.
            cmpCntr = [0,0]
            # i+sizCntr가 N 이상이면, 영역이 하나밖에 없고 이미 기록되어 있으므로:
            if i+sizCntr < N:
                while True:
                    # 0번 작업영역을 모두 기록했다면, 1번 작업영역의 남은 요소를 모두 기록합니다.
                    if cmpCntr[0] == sizCntr:
                        mrgArr[1-switch][i+sizCntr+cmpCntr[1]:i+sizCntr*2] = mrgArr[switch][i+sizCntr+cmpCntr[1]:i+sizCntr*2]
                        break
                    # 1번 작업영역을 모두 기록했거나, 리스트의 끝까지 기록했다면, 0번 작업영역의 남은 요소를 모두 기록합니다.
                    if (cmpCntr[1] == sizCntr) or (i+sizCntr+cmpCntr[1] == N):
                        mrgArr[1-switch][i+cmpCntr[0]+cmpCntr[1]:i+sizCntr*2] = mrgArr[switch][i+cmpCntr[0]:i+sizCntr]
                        break
                    # 0번 작업영역과 1번 작업영역에서 대상이 되는 수를 비교하여, 더 작은 것을 기록합니다.
                    if mrgArr[switch][i+cmpCntr[0]] < mrgArr[switch][i+sizCntr+cmpCntr[1]]:
                        mrgArr[1-switch][i+cmpCntr[0]+cmpCntr[1]] = mrgArr[switch][i+cmpCntr[0]]
                        cmpCntr[0] += 1
                    else:
                        mrgArr[1-switch][i+cmpCntr[0]+cmpCntr[1]] = mrgArr[switch][i+sizCntr+cmpCntr[1]]
                        cmpCntr[1] += 1
        # 작업영역의 크기를 2배로 합니다. 이때 작업영역의 크기가 입력받은 값의 갯수 이상이면 정렬이 끝났으므로 None을 반환합니다.
        sizCntr *= 2
        if sizCntr >= N:
            return None

mrgArr = [[],[]]
sizCntr = 1
switch = 1
N = int(stdin.readline())
for i in range(0,N):
    mrgArr[0].append(int(stdin.readline()))
mrgArr[1] = mrgArr[0][:]
Merge()
for i in range(0,N):
    print(mrgArr[1-switch][i])

dlwlsdn3642 2년 전 1

가장 추천하는건 파이썬을 사용하시니 sorted() 함수나 sort() 함수를 활용하는 것입니다.

그리고 파이썬은 인터프리터 언어이기 때문에 원래 느려서 이런 경우와 브루트포스 알고리즘같은 노가다가 있을 때는 pypy3로 하셔야 유의미한 결과를 얻을 수 있습니다.

bak9234 2년 전 1

pypy3으로 해봐야겠네요. 답변 주셔서 감사합니다!

bak9234 2년 전 1

PyPy3으로 제출한 후 코드에서 오류가 있는 부분 찾아서 완전히 해결했습니다. 정말 감사합니다 :)

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

문제

문제

출처

ICPC

파이썬 병합 정렬 - 시간 초과

bak9234 2년 전 0

dlwlsdn3642 2년 전 1

bak9234 2년 전 1

bak9234 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말