🔥

문제

N개의 수가 주어질 때, 수들을 오름차순으로 정렬한 결과를 출력하라

입력

첫 줄에 수의 개수 N이 주어진다. (1≤N≤1,000,000)


둘째 줄부터 N개 줄에 걸쳐 수가 주어진다. 주어지는 수는 0 이상 1,000,000 이하의 정수이다.

출력

N개 줄에 걸쳐, 한 줄에 하나씩 수들을 오름차순으로 정렬한 결과를 출력한다.

예제 1 입력

5
3
1
1
3
4

예제 1 출력

1
1
3
3
4

Source

n = int(input())
tree = [0 for _ in range(n + 1)]

size = 0

def add(x):
    global size
    size += 1
    tree[size] = x

    idx = size
    while(idx > 1):
        if(tree[idx] < tree[idx // 2]):
            tree[idx], tree[idx // 2] = tree[idx // 2], tree[idx]
        else:
            break

        idx //= 2

def remove():
    global size
    if(size == 0):
        return 0

    top = tree[1]
    tree[1] = tree[size]
    tree[size] = 0
    size -= 1

    idx = 1
    while(idx * 2 <= size):
        l = idx * 2
        r = idx * 2 + 1

        # r이 존재하지 않거나, 왼쪽 자식이 오른쪽 자식보다 작고
        # x값이 왼쪽 자식보다 크면
        if((r > size or tree[l] < tree[r]) and tree[idx] > tree[l]):
            tree[idx], tree[l] = tree[l], tree[idx]
            idx = l
        # r이 존재하고 x값이 오른쪽 자식보다 크면
        elif(r <= size and tree[idx] > tree[r]):
            tree[idx], tree[r] = tree[r], tree[idx]
            idx = r
        else:
            break

    return top

for i in range(1, n + 1):
	add(int(input()))
for i in range(1, n + 1):
    print(remove())

참고: 시간 초과

참고