[Python] BOJ(백준) 2075번 - N번째 큰 수

링크

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

난이도(solved.ac 참고)

골드5

풀이

메모리 제한이 없다면, 걍 실버급도 안되는 문제라고 생각했다. 처음에 그냥 input값 받은 것들 전부 하나로 합친 다음에 거기서 n-1번째 인덱스를 추출하면 되지 않나? 라고 생각해서 바로 제출했는데 역시 메모리 초과가 떴다. 하기야 그렇게 풀 수 있으면 이게 골드 5일수가 없지..
메모리가 초과된다는 건, 결국 저장되는? 값이 많다는 얘기라고 생각한다. 그래서, input으로 다 받아오지 않고 처음에 한 줄 받아온 뒤 그것을 힙에 넣었다. 그다음에 1부터 n까지 반복문을 돌면서 돌때마다 input을 받아왔고, 이중 반복문을 통해 최소힙의 가장 작은 값보다 받아온 리스트 내부의 값이 더 클 경우 내부의 값을 넣은 뒤 pop을 해줘서 최소 값을 제거했다.

push가 pop보다 먼저 와야 되는 이유?
[35, 48, 41, 49, 52]가 있다고 해보자. 여기서 34가 들어온다고 한다면..? 우리가 의도한 바에 따르면 34가 들어왔다가 바로 나가야된다. 왜냐면 가장 작은 35보다도 작기 때문이다. 근데 pop이 먼저 들어온다면 35가 빠지고 그이후에 push에 따라 34가 들어가게 된다. 이는 결국 의도한 바대로 작동하지 않게 된다.
생각해보니 if문에서 이미 0번째 인덱스와의 비교가 일어나기 때문에 pop과 push의 순서는 상관이 없다. if문이 없다면 push가 먼저 와야하는 게 맞다.