백준#2075 N번째 큰 수 in Python

2075번: N번째 큰 수

이 문제의 핵심은 입력으로 주어지는 수를 모두 배열에 때려 박아서 정렬하는 것보다 더 효율적인 방법이 무엇인지 고민하는 것이다. 여기서, 'N번째 큰 수'란, 'N개의 수들 중 가장 작은 수'라는 것을 깨닫고 나면 문제가 쉽게 풀린다. 

---

문제 예시처럼 N=5라고 가정할 때, 최대 크기가 5인 리스트를 만들었다. 

└ 크기가 5보다  작으면 일단 숫자를 넣고, 그 외의 경우에는 (크기가 5인 경우) 다음 행위를 실행한다.

리스트의 크기가 5일 때 새로운 숫자를 만나면 최소값과 비교한다.

└ 예시를 들어보면 최소값과 비교하는 이유가 쉽게 이해된다.

└ 우리는 전체 입력 값 중 5번째로 큰 수를 찾아야 하므로, 현재 리스트에 들어있는 숫자들보다 작은 수는 필요가 없다. 현재 리스트에 들어있는 숫자들 중 최소 한 숫자보다는 커야 (즉, 리스트의 최소값보다는 커야) 몇 번째로 큰 지 논할 의미가 생긴다.

따라서 새로운 숫자가 최소값보다 크다면, 리스트에서 최소값을 없애고 새로운 숫자를 삽입한다.

└ 이러한 과정을 반복함으로써 '지금까지 만난 수들 중 가장 큰 수 5개의 목록'을 리스트에 유지한다.

---

n = int(input())
input_num, pq = [], []
for _ in range(n):    
    input_num.append(list(map(int, input().split(" "))))

for i in input_num:
    for j in i:
        pq.sort()
        if len(pq) < n:
            pq.append(j)
        else:
            if j > pq[0]:
                pq.remove(pq[0])
                pq.append(j)
            else:
                pass

print(pq[0])