4/19 스터디 문제
1번 문제.
https://www.acmicpc.net/problem/2075
-> N번째 큰 수
1-1번 문제 풀이 코드 (메모리 초과)
import sys
from collections import deque
n = int(sys.stdin.readline())
nums = deque()
for _ in range(n):
nums.append(deque(map(int, sys.stdin.readline().rstrip().split())))
list = []
for i in range(n):
for j in range(n):
list.append(nums[i][j])
list.sort(reverse=True)
print(list[n-1])
=======================================================
메모리 초과!!!
다른 블로그들을 찾아보니, 힙큐를 사용해서 푸는 것을 추천한다.
우선순위 큐과 힙
1-2번 문제 풀이 코드(정답)
import sys
import heapq
# nxn 보드 입력
n = int(sys.stdin.readline())
# 힙 숫자들의 리스트
num_list = []
for _ in range(n):
# n번 숫자들을 입력 받음
numbers = list(map(int, sys.stdin.readline().rstrip().split()))
# 저장할 리스트에 값이 없으면
if not num_list:
# 입력 받은 숫자들을 하나씩
for num in numbers:
# num_list에 숫자(num)를 넣는다.
# heappush를 이용해서 리스트에 최솟값부터 담긴다.
heapq.heappush(num_list, num)
# print(num_list)
else:
for num in numbers:
# 만약 리스트 내에서 최솟값이 입력 받은 수보다 작으면
if num_list[0] < num:
# 입력 받은 수를 num_list에 넣어준다.
heapq.heappush(num_list, num)
# print(num_list)
# 그리고 최솟값(num_list[0])을 하나씩 제거
heapq.heappop(num_list)
# print(num_list)
# print(num_list) -> 최솟값들을 하나씩 제거하고나면, num_list에는 가장 큰 수 n개가 순서대로 남아 있다.
print(num_list[0])
[12][7, 12]
[7, 12, 9][7, 12, 9, 15]
[5, 7, 9, 15, 12]
그 다음에 13이 온다.
[5, 7, 9, 15, 12, 13][7, 12, 9, 15, 13] 최솟값 5 제거 후 그 다음 최솟값이 앞에 채워짐
[7, 12, 8, 15, 13, 9][8, 12, 9, 15, 13]
[8, 12, 9, 15, 13, 11][9, 12, 11, 15, 13]
[9, 12, 11, 15, 13, 19][11, 12, 19, 15, 13]
[11, 12, 19, 15, 13, 21][12, 13, 19, 15, 21]
[12, 13, 19, 15, 21, 26][13, 15, 19, 26, 21]
[13, 15, 19, 26, 21, 31][15, 21, 19, 26, 31]
[15, 21, 16, 26, 31, 19][16, 21, 19, 26, 31]
[16, 21, 19, 26, 31, 48][19, 21, 48, 26, 31]
[19, 21, 28, 26, 31, 48][21, 26, 28, 48, 31]
[21, 26, 28, 48, 31, 35][26, 31, 28, 48, 35]
[26, 31, 28, 48, 35, 52][28, 31, 52, 48, 35]
[28, 31, 32, 48, 35, 52][31, 35, 32, 48, 52]
[31, 35, 32, 48, 52, 41][32, 35, 41, 48, 52]
[32, 35, 41, 48, 52, 49][35, 48, 41, 49, 52]
=======================================================
힙큐 문제들을 몇 번 더 풀어봐야 할 듯 하다.
Author And Source
이 문제에 관하여(4/19 스터디 문제), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hey_junie/419-스터디-문제저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)