[baekjoon] 백준 2075번(파이썬): N번째 큰 수

문제

2075번: N번째 큰 수

알고리즘

- 리스트 안에 미리 제일 작은 수를 넣어놓는다.

- 비교할 수도 제일 작은 수로 초기화시킨다.

- 각 행의 열의 크기를 비교하면서 타겟보다 큰 수라면 큰 수를 heap 리스트에 추가한다.

- 다음으로 heap 리스트에 제일 작은 수를 팝하고 그 수를 타겟으로 바꾼다.

- n번째로 큰 값을 구하는 것으로 n번째보다 큰 수이면 리스트에 제일 작은 수를 팝한 후 큰 수를 heap 리스트에 넣는 방법을 문제를 수행했다.

코드

import heapq
import sys

n = int(sys.stdin.readline())
heap = [-1000000000] * n # heap 리스트에 제일 작은 수를 미리 넣는다.
target = -1000000000 # 비교할 수 (제일 작은 수로 초기화)

for _ in range(n):
    row = list(map(int, sys.stdin.readline().split()))
    # 각 행의 열의 크기를 비교한다.
    for i in row:
        # 타겟보다 큰 수이면
        if target < i:
            heapq.heappush(heap, i) # 큰 수를 힙에 추가한다.
            target = heapq.heappop(heap) # 힙에서 제일 작은 수를 팝하고 그 수를 타겟으로 바꾼다.

# 힙에서 제일 작은 수가 n 번째로 작은 수
print(heapq.heappop(heap))

 

실패한 코드(메모리 초과)

import heapq
import sys

n = int(sys.stdin.readline())
heap = []

for _ in range(n):
    row = list(map(int, sys.stdin.readline().split()))
    for i in row:
        heapq.heappush(heap, (-i, i))

for _ in range(n - 1):
    heapq.heappop(heap)[1]

print(heapq.heappop(heap)[1])

표의 크기 n의 범위가 1보다 크거나 같고 1500보다 작거나 같기 때문에 시간 복잡도만을 생각해서 O(N^2)으로 문제를 풀어봤는데 메모리가 제한이 12mb라서 그런지 메모리 초과가 나오면서 문제를 틀리게 되었다. 

 

실패한 코드(틀렸습니다.)

import heapq
import sys

n = int(sys.stdin.readline())
heap = [0] * n
target = 0
for _ in range(n):
    row = list(map(int, sys.stdin.readline().split()))
    for i in row:
        if target < i:
            heapq.heappush(heap, i)
            target = heapq.heappop(heap)
            
print(heapq.heappop(heap))

위 코드는 정답 코드 이전에 코드이다. 정답 코드와 유사하지만 표에 적힌 수의 범위를 고려하지 않았기 때문에 틀리게 되었다. 표에 적힌 수의 범위는 -10억보다 크거나 같고 10억보다 작거나 같은 정수이다. 따라서 타겟의 수와 heap 리스트에 미리 넣어 놓을 수를 제일 작은 수인 -10억으로 초기화시키고 실행시켜야 한다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법