★백준/1655 가운데를 말해요 / 우선순위큐

가운데를 말해요 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.1 초 (하단 참고)

128 MB

46404

13493

10163

30.553%

문제

백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

출력

한 줄에 하나씩 N줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.

예제 입력 1 복사

7
1
5
2
10
-99
7
5

예제 출력 1 복사

1
1
2
2
2
2
5

 

---

풀이

/*
외치는 수가 10만개나 된다. 이중반복문을 이용하면 시간초과가 될것이다.
우선순위큐 2개를 이용해서 구현해본다, 중앙 값을 뽑아내기위해
왼쪽에는 최대힙을 이용한 우선순위큐
오른쪽에는 최소힙을 이용한 우선순위큐를 이용한다.
홀수번째 수의 입력이면 왼쪽에 값을 넣고,
짝수번째 수의 입력이면 오른쪽에 값을 넣는다.

왼쪽에 값을넣고, 왼쪽의 가장큰값(우선순위가 가장높은값)과 오른쪽의 가장 작은값(우선순위가 가장높은값)을 비교해서 왼쪽의 값이 더 크다면 각각 큐에서 값을 빼서 바꿔 넣어준다.
오른쪽에 값을 넣을때도 , 오른쪽 최소값이 왼쪽 최대값보다 작을때 각각 값을 빼서 나눠 넣어준다.
 */

들어오는 값이 1,2,3,4,5.... 일때 동작방식

1은 홀수번째 삽입이므로 왼쪽으로 들어가고

2는 짝수번째 삽입이므로 오른쪽에 들어간다.

그리고 3은 홀수번째 삽입이므로 왼쪽에 넣었더니

왼쪽의 최대값이 오른쪽 최소값보다 크게됬다.

그 경우 양쪽값을빼서 각각 큐에 넣어준다.

-> 위의 동작을 반복

 

중요.

왼쪽에 값을 넣을때( 홀수번째 값 삽입) , 오른쪽에 값을 넣었을때(짝수번째 값 삽입) 

둘다 왼쪽 최대값이 오른쪽 최소값보다 큰지 체크한다.

 

 

import java.io.*;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;


public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    /*
    외치는 수가 10만개나 된다. 이중반복문을 이용하면 시간초과가 될것이다.
    우선순위큐 2개를 이용해서 구현해본다, 중앙 값을 뽑아내기위해
    왼쪽에는 최대힙을 이용한 우선순위큐
    오른쪽에는 최소힙을 이용한 우선순위큐를 이용한다.
    홀수번째 수의 입력이면 왼쪽에 값을 넣고,
    짝수번째 수의 입력이면 오른쪽에 값을 넣는다.

    왼쪽에 값을넣고, 왼쪽의 가장큰값(우선순위가 가장높은값)과 오른쪽의 가장 작은값(우선순위가 가장높은값)을 비교해서 왼쪽의 값이 더 크다면 각각 큐에서 값을 빼서 바꿔 넣어준다.
    오른쪽에 값을 넣을때도 , 오른쪽 최소값이 왼쪽 최대값보다 작을때 각각 값을 빼서 나눠 넣어준다.
     */
    static PriorityQueue<Integer> leftQ = new PriorityQueue<>(Collections.reverseOrder());
    static PriorityQueue<Integer> rightQ = new PriorityQueue<>();
    static int n;


    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        n = Integer.parseInt(br.readLine());
    }

    static void solve() throws IOException {
        for (int i = 1; i <= n; i++) {
            int input = Integer.parseInt(br.readLine());
            if (i % 2 != 0) { // 홀수번째 수를 입력시 왼쪽 우선순위큐에 삽입하고, 왼쪽 최대값과 오른쪽 최소값 비교해서 다르면 스위치
                leftQ.add(input);
                changeNumber();
                bw.write(leftQ.peek() + "\n");
            } else {
                rightQ.add(input);
                changeNumber();
                bw.write(leftQ.peek()+"\n");
            }
        }



    }

    static void changeNumber() { // 왼쪽 최대값과 오른쪽 최소값을 비교해서 왼쪽이 더 크면 각각 값을꺼내 바꿔 넣어준다. -> 왼쪽이든 오른쪽이든 값을 넣어줄때마다 실행
        if (!leftQ.isEmpty() && !rightQ.isEmpty()) { //둘다 비어있지않아야한다. 한쪽이라도 비어있으면 아무일도 일어나지않음
            int leftNumber = leftQ.peek();
            int rightNumber = rightQ.peek();

            if (leftNumber > rightNumber) {
                leftNumber = leftQ.poll();
                rightNumber = rightQ.poll();
                leftQ.add(rightNumber);
                rightQ.add(leftNumber);
            }
        }

    }

}

 

다른 사람 풀이

방식은 같으나

다른 코드.

https://dragon-h.tistory.com/6

[백준 1655 : JAVA] 가운데를 말해요 / PriorityQueue