Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
Tags
- 열거형
- 인터페이스
- Encapsulation
- 와일드카드
- inheritance
- 다형성
- 생성자
- 프림알고리즘
- 객체 지향
- Scanner
- 최소신장트리
- java
- 버퍼비우기
- 상속
- abstract
- 내부 클래스
- 17472
- Final
- 추상화
- 객체지향
- this
- nextInt
- enum
- 추상 클래스
- 캡슐화
- python
- 백준
- 제네릭
- polymorphism
Archives
- Today
- Total
쫑쫑이의 블로그
백준 1655 가운데를 말해요 Java [우선순위 큐] 본문
https://www.acmicpc.net/problem/1655
1655번: 가운데를 말해요
첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1
www.acmicpc.net
가운데 값을 기준으로 왼쪽에 최대 힙, 오른쪽에 최소 힙을 만들어주고
두 힙의 사이즈가 같거나 왼쪽이 1 더 크게 만들어서 왼쪽의 peek 값을 출력값에 넣어준다
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> left = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<Integer> right = new PriorityQueue<>();
int Z = Integer.parseInt(br.readLine());
left.add(Z);
sb.append(Z).append("\n");
for (int n = 1; n < N; n++) {
Z = Integer.parseInt(br.readLine());
if (left.peek() > Z) {
left.add(Z);
if (left.size() > right.size() + 1) {
right.add(left.poll());
}
} else {
right.add(Z);
if (right.size() > left.size()) {
left.add(right.poll());
}
}
sb.append(left.peek()).append("\n");
}
sb.setLength(sb.length() - 1);
System.out.println(sb);
}
}
'알고리즘 > 백준' 카테고리의 다른 글
백준 1717 집합의 표현 Java [분리집합, Union find] (0) | 2022.11.22 |
---|---|
백준 10986 나머지 합 Java [누적합] (0) | 2022.11.21 |
백준 17425 약수의 합 Java [에라토스테네스의 체, 누적합] (0) | 2022.11.19 |
백준 7579 앱 Java [DP, 배낭문제] (0) | 2022.11.17 |
백준 2467 용액 Java [투포인터] (0) | 2022.11.16 |