우선순위큐
-
[백준] 17086 아기 상어 2 with PythonPS 2022. 7. 17. 22:03
📌 BOJ 17086 아기 상어 2 💡 조건 N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다. N과 M(2 ≤ N, M ≤ 50) 어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다. 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다. 안전 거리가 가장 큰 칸을 구하는 문제. heapq, 우선순위 큐 유형의 문제 🖥 소스 코드 from sys import stdin import heapq n, m =..
-
[백준] 22252 정보 상인 호석 with PythonPS 2022. 5. 18. 02:26
📌 BOJ 22252 정보 상인 호석 💡 조건 관찰하면서 얻은 정보는 총 $Q$ 개이다. 각 정보는 다음의 2가지 중 하나이다. 1 Name k C_1, C_2, ..., C_k : 이름이 [Name]인 고릴라가 k 개의 정보를 얻었으며, 각 가치는 C_1 부터 C_k 이다. 2 Name b : 호석이가 이름이 [Name]인 고릴라에게 b 개의 정보를 구매한다. 이때 고릴라가 가진 정보들 중 가장 비싼 b 개를 구매하며, 고릴라가 가진 정보가 b개 이하이면 가진 모든 정보를 구매한다. 고릴라들이 정보를 얻는 사건과 호석이가 거래하는 정보가 시간순으로 주어진다. 첫 번째 줄에는 쿼리의 개수 Q가 주어진다. Q 개의 줄에 걸쳐서 각 줄에 쿼리가 주어진다. 쿼리는 1이나 2로 시작한다. 1로 시작하는 경우에는..
-
[백준] 2075 N번째 큰 수 with PythonPS 2022. 2. 21. 17:05
📌 BOJ 2075 N번째 큰 수 💡 조건 N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. 표에 채워진 수는 모두 다르다. N(1 ≤ N ≤ 1,500) 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. 자료구조 응용, 우선순위 큐 활용, 정렬 유형의 문제 🖥 소스 코드 from sys import stdin import heapq n = int(stdin.readline()) q = [] cnt = 0 for _ in range(n): data = list(map(int, stdin.readline().split())) for j in data: if cnt != n: heapq.heap..
-
[백준] 13334 철로 with PythonPS 2021. 10. 25. 23:56
📌 BOJ 13334 철로 💡 조건 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000) n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. −100,000,000 ≤ hi ≤ 100,000,000 −100,000,000 ≤ oi ≤ 100,000,000 oi != hi 철로의 길이를 나타내는 정수 d (1 ≤ d ≤ 200,000,000) 집과 사무실 모두가 철로 길이 안에 들어갈 수 있는 최대의 개수를 구하는 문제. 우선순위 큐, 즉 자료구조를 활용하는 문제. 🖥 소스 코드 from sys import stdin import heapq n = int(stdin.readline()) roads, data = [], [] for _ in range(n): data.append(sorted(..