-
Java 1655 가운데를 말해요PS 2023. 8. 25. 10:25
https://www.acmicpc.net/problem/1655
1655번: 가운데를 말해요
첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1
www.acmicpc.net
시간 제한이 0.1초이기에 원소가 들어올 때 마다 중간값을 찾는다면 시간초과가 날 것이다.(N이 최대 100,000이기 때문에)
그래서 우선순위 큐를 두개를 사용하여 해당 문제를 풀이하였다.
문제의 예시처럼 1, 5, 2 10, -99, 7, 5 가 입력 값으로 주어질 때 원소 하나당 어떤 작업이 이루어지는지 살펴보겠다.
우선 1이 들어올 때 모든 큐에 값이 없으므로 maxHeap에 원소를 넣어준다 그럼 큐 두개의 상태는 아래와 같다.
1번째 원소가 들어온 뒤 - maxHeap : 1, minHeap : X;
2번째 원소가 들어온 뒤 - maxHeap : 1, minHeap : 5;
3번째 원소가 들어온 뒤 - maxHeap : 1,2 minHeap : 5;
이때 maxHeap의 peek한 값과 minHeap의 peek한 값을 비교하여 maxHeap과 minHeap의 스왑이 일어난다.
이 과정을 거치면 두 큐에 원소가 제대로 삽입되었기에 maxHeap의 값을 peek하여 출력한다.
우선순위 조건이 서로 다른 두개의 큐를 사용한다면 낮은 수부터 높은 수까지 정렬된 상태로 가운데에서 원소의 접근에 걸리는 시간복잡도가 상수시간이기 때문에 해당 문제를 풀이할 수 있었다.
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.*; 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> minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2); PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1); for(int i = 0; i < n; i++){ int num = Integer.parseInt(br.readLine()); if(maxHeap.size() == minHeap.size()){ maxHeap.add(num); }else { minHeap.add(num); } if(!maxHeap.isEmpty() && !minHeap.isEmpty()) { if (maxHeap.peek() > minHeap.peek()) { int tmp = minHeap.poll(); minHeap.add(maxHeap.poll()); maxHeap.add(tmp); } } sb.append(maxHeap.peek()).append("\n"); } System.out.println(sb); } }
'PS' 카테고리의 다른 글
Java 1654 랜선 자르기 (0) 2023.08.29 Java 11967 불켜기 (0) 2023.08.25 Java 2636 치즈 (0) 2023.08.22 Java 1976 여행 가자 (0) 2023.08.11 Java 11404 플로이드 (0) 2023.08.08