1655번 - 가운데를 말해요
문제 풀이 시간 : 2시간
문제 요약
- N 개의 수를 외친다.
- 정수를 하나씩 외칠때마다 지금까지 말한 수 중 중간값을 말해야한다.
- 외친 수가 짝수 개라면 중간에 있는 두 수 중 작은 수를 말한다.
문제 풀이
처음에는 그냥 막무가내로 정렬을 해서 가운데 출력하면 되는거 아닌가?
했는데
시간 제한이 0.1초여서 불가능하다는걸 깨달았다.
그래서 뭔가 우선순위큐를 사용해야겠다고 생각했는데, 우선순위큐를 사용하면 가운데를 어떻게 출력할까? 라고 고민을 해보았다.
그래서 생각했던게 우선순위큐를 하나 만들어서 중간 값을 찾는 것이다.
for (int i = 0; i < N; i++) {
pq.add(Integer.parseInt(br.readLine()));
List<Integer> temp = new ArrayList<>();
int mid = pq.size()/2;
int size = pq.size();
for (int j = 0; j < mid; j++) {
temp.add(pq.poll());
}
if(size%2!=0){
System.out.println(pq.peek());
}
else{
System.out.println(Math.min(pq.peek(), temp.get(temp.size()-1)));
}
pq.addAll(temp);
}매번 이런 식으로 우선순위 큐에서 절반만큼을 리스트에 빼내어 가운데 수를 출력하고 다시 우선순위큐에 집어넣는 방식이다.
당연하게도 시간초과가 났다.
너무 비효율적인 방식인 것 같긴하다.
그렇게 여러가지 방법을 시도해보았지만 도저히 풀 수 없어서
똑똑하신 구글의 힘을 빌렸다.
이 문제는 두개의 우선순위 큐를 사용해야하는 문제였다.
minHeap, maxHeap 두가지 우선순위 큐를 사용하여 가운데 수를 빠르게 찾는 것인데,
먼저, 두 개의 우선순위 큐의 크기가 같다면 maxHeap에 값을 추가한다.
두 개의 우선순위 큐의 크기가 다르다면 minHeap에 값을 추가한다.
그리고 매번 maxHeap의 top이 가운데 값이 되게 된다.
그렇다면 왜 위와 같이 동작할까?
쉽게 생각하면 maxHeap에는 가운데 수를 기준으로 작은 수들, minHeap에는 가운데 수를 기준으로 큰 수들이 들어간다고 생각하면 된다.
예를 들어,
10 8 5 3 5 -1 의 순서로 입력이 들어온다고 생각하자.
- 10 입력
- 8 입력
위와 같이 입력이 들어오지만, 원래 두개의 우선순위 큐의 크기가 다른 상태에서
입력된 값이 maxHeap의 top 보다 작기 때문에 두 값을 스왑한다.
- 5 입력
- 3 입력
입력된 값이 maxHeap의 top인 8보다 작기 때문에 두 값 스왑
- 5 입력
- -1 입력
입력된 값이 maxHeap의 top인 5보다 작기 때문에 두 값 스왑
위와 같이 결국 가운데 수를 기준으로 작은 수들은 maxHeap으로, 큰 수들은 minHeap으로 모이게 되어 결국 가운데수를 출력할 수 있게 된다.
위 내용을 참고하여 코드를 다시 짜본다면 아주 간단하게 풀 수 있다.
정답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
PriorityQueue<Integer> min = new PriorityQueue<>();
PriorityQueue<Integer> max = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int i = 0; i < N; i++) {
int input = Integer.parseInt(br.readLine());
if (min.size() == max.size()) {
if(!min.isEmpty() && min.peek()<input){
max.add(min.poll());
min.add(input);
}
else{
max.add(input);
}
}
else{
if(!max.isEmpty() && max.peek()>input){
min.add(max.poll());
max.add(input);
}
else{
min.add(input);
}
}
sb.append(max.peek()).append("\n");
}
System.out.println(sb);
}
}함께 읽으면 좋은 글
5430번 - AC
함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…
1966번 - 프린터 큐
여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…
1158 - 요세푸스 문제
1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.
2164번 - 카드2
1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.