99클럽 코테 스터디 20일차 TIL

오늘의 학습 키워드

힙

과제

문제

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

12	7	9	15	5
13	8	11	19	6
21	10	26	31	16
48	14	28	35	25
52	20	32	41	49

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

출력

첫째 줄에 N번째 큰 수를 출력한다.

예제 입력 1 복사

5
12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49

예제 출력 1 복사

35

풀이 과정

1. import heapq: 파이썬의 힙 큐 모듈을 가져옵니다. 힙 자료구조를 사용하기 위함입니다.
2. heap = []: 빈 리스트를 생성합니다. 이 리스트는 최소 힙으로 사용될 것입니다.
3. n = int(input()): 사용자로부터 n을 입력받습니다. 이 n은 "몇 번째로 큰 수를 찾을 것인지"를 결정합니다.
4. 그 다음 반복문에서:
5. 공백으로 구분된 숫자들을 입력받습니다
6. 각 숫자에 대해:
7. 만약 힙의 크기가 n보다 작으면: 숫자를 그냥 힙에 넣습니다
8. 힙의 크기가 n이면: 새로운 숫자가 힙의 최솟값(heap[0])보다 클 때만 교체합니다
9. 힙에서 최솟값을 꺼내고(heappop)
10. 새로운 숫자를 넣습니다(heappush)
11. 마지막에 heap[0]를 출력하면 그것이 n번째로 큰 수입니다.

제출 코드 (python)

import heapq

heap = []
n = int(input())

for _ in range(n):
    numbers = map(int, input().split())
    for number in numbers:
        if len(heap) < n: 
            heapq.heappush(heap, number)
        else:
            if heap[0] < number:
                heapq.heappop(heap)
                heapq.heappush(heap, number)
print(heap[0])

오늘의 회고

• 힙큐 모들이라는 것을 처음 알았는데 성능도 나쁘지 않고 좋을 것 같다.

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