테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== N번째 큰 수 ======

===== 풀이 =====
  * 기본적인 방법은 그냥 전체 입력을 다 리스트에 저장해놓고서 정렬하거나 선택알고리즘을 적용하는 것이다. 하지만 이 문제에서는 메모리 제한이 걸려있어서 전체 입력을 리스트에 저장하지 않는 방법이 필요하다. 
    * 메모리 제한이 좀 어정쩡한데.. [[https://www.acmicpc.net/board/view/36675]] 에 따르면, 원래 문제 의도는 N^2개의 수를 메모리에 모두 담는것을 허용하되 타이트하게 잡는 것이었다고 한다. 그래서 c++ 기준으로는 입력값을 모두 메모리에 저장해서 푸는 것도 가능한것 같은데, 파이썬은 그렇게는 안되는것 같다.
  * [[ps:우선순위큐#가장 큰 수 k개 찾기|우선순위 큐 - 가장 큰 수 k개 찾기]] 방법을 적용한다. 처음 N개의 원소로 최소힙을 만들고, 새 원소를 힙에 push하고 최소값을 pop 하는것을 반복한다. 이렇게 하면 힙안의 원소 갯수는 N개로 유지되고, 이 N개의 원소들이 여태까지 봤던 원소들중 에서 가장 큰 원소들이다. N번째로 큰 원소는 당연히 top에 있는 원소. 시간복잡도는 O(N^2logN). 

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 2075. N번째 큰 수".

- Problem link: https://www.acmicpc.net/problem/2075
- Solution link: http://www.teferi.net/ps/problems/boj/2075
"""

import heapq
import sys

INF = float('inf')


def main():
    N = int(sys.stdin.readline())
    heap = [-INF] * N
    for _ in range(N):
        nums = [int(x) for x in sys.stdin.readline().split()]
        for num in nums:
            if num > heap[0]:
                heapq.heapreplace(heap, num)
    print(heap[0])


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_5}}