1. 백준 1655: 가운데를 말해요
1655번: 가운데를 말해요
첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1
www.acmicpc.net
Queue를 사용하여 중앙값을 찾는 방법
중앙값 기점으로 maxPq(Heap) / minPq(Heap) 이용하기
maxPq: 중앙값보다 작은 값 저장 / minPq: 중앙값보다 큰 값 저장
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> minPq = new PriorityQueue<>();
PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < n; i++) {
int num = Integer.parseInt(br.readLine());
if (maxPq.isEmpty() || maxPq.peek() >= num) {
maxPq.offer(num);
} else {
minPq.offer(num);
}
if (maxPq.size() > minPq.size() + 1) {
minPq.offer(maxPq.poll());
} else if (minPq.size() > maxPq.size()) {
maxPq.offer(minPq.poll());
}
if (maxPq.size() == minPq.size()) {
sb.append(Math.min(maxPq.peek(), minPq.peek())).append("\n");
} else {
sb.append(maxPq.peek()).append("\n");
}
}
System.out.print(sb);
}
}
2. 백준 12764: 싸지방에 간 준하
10% 오답으로 꽤나 고통 받았던 문제.
이유는 내가 짠 코드가 비어있는 자리 중에서 번호가 작은 자리부터 앉는다는 조건을 만족하지 않았기 때문
많은 분들이 나와 같은문제를 겪으신 것 같아 질문게시판에 반례가 여러 개 올라와 있다.
만약 나와 같은 난관에 봉착하시는 분들이 있다면,,, 반례 돌려보면서 조건을 모두 만족하도록 다시 코드를 짜보시길!
노션에도 반례 정리해놓긴 함
12764번: 싸지방에 간 준하
첫째 줄에 사람의 수를 나타내는 \(N\)이 주어진다. \((1 \le N \le 100,000)\) 둘째 줄부터 \(N\)개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 \(P\)와 종료 시각 \(Q\)가 주어진다. \((0 \le P \lt Q \le 1,000
www.acmicpc.net
3. 프로그래머스: 다리를 지나는 트럭
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
⚒️자세한 풀이 및 코드는 노션에
02.22 CodingStudy- Queue | Notion
🛻다리를 지나는 트럭
yeahzz.notion.site
'Algorithms > study log' 카테고리의 다른 글
[Greedy] 연속되는 조건이 있는 문제 (1) | 2024.03.17 |
---|---|
[java] 트리와 DFS (0) | 2024.02.26 |
[java] 플로이드-워셜 알고리즘 (0) | 2024.02.06 |
[java] 벨만포드 알고리즘 (0) | 2024.02.06 |
[java] 다익스트라 알고리즘 (0) | 2024.02.01 |