[BOJ] 1655 - 가운데를 말해요

황규빈·2022년 1월 31일
0

알고리즘

목록 보기
19/33

💎 문제


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

예를 들어 백준이가 동생에게 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줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.

💎 풀이 방법


우선 순위 큐를 이용하여 중간 값을 찾아내는 방법의 문제였다. 아이디어가 직접 제대로 떠오르지 않아 두 개의 maxheap, minheap을 이용하여 중간 값을 구할 수 있다는 점을 인지하고 문제를 접하였다!!

우선 시간초과를 줄이기 위해서 반복문에서의 입출력문이 들어가는 것을 고려하여

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

위와 같이 처리를 해주었다!!

    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;

우선 순위 큐를 이용하여 minheap과 maxheap을 구현했다. 이전 게시글들에서 사용하였던 greater를 이용하여 오름차순인 minheap으로 top이 가장 작은 숫자를 가리키도록 하였다. 또한 maxheap은 우선순위 큐를 그대로 선언하여 top이 그 큐에 최대를 가리키도록 하였다. 이러한 두 우선 순위 큐를 번갈아가면서 값을 넣어주면서 중간 값을 정할 수 있는 것이다.

    for(int i = 0;i < N;i++){
        int temp;
        cin >> temp;
        if(maxHeap.empty())
            maxHeap.push(temp);
        else{
            if(maxHeap.size() > minHeap.size())
                minHeap.push(temp);
            else
                maxHeap.push(temp);
            
            if(maxHeap.top() > minHeap.top()){
                int x = maxHeap.top();
                int y = minHeap.top();
                maxHeap.pop();
                minHeap.pop();
                maxHeap.push(y);
                minHeap.push(x);
            }
        }
        cout << maxHeap.top() << "\n";
    }

maxheap과 minheap에 번갈아가면서 값을 넣어주면서 maxheap과 minheap의 top을 비교하여 준다. maxheap의 최대 값은 minheap의 최솟 값보다 작게 하여 이에 어긋나게 되면 바꿔주는 식으로 작성하였다. 예를 들어, 1을 처음 넣게 되면 maxheap의 top은 1로 중간 값을 1로 설정할 것이다. 그 다음 5를 넣게 된다면 maxheap에 이미 값 하나가 들어가여 minheap에 5를 넣어주고 중간 값은 1과 5중 minheap의 top보다 작은 maxheap의 top을 출력해주는 것이다.

maxheap의 topminheap의 top을 이용해서 maxheap의 크기가 더 작기 때문에 짝수일때도 고려하여 중간 값을 구할 수 있다!! 단순하게 생각하면 쉬운 문제였는데 두 개의 힙을 이용하여 그 중간 값을 각각의 힙의 top을 이용하여 표현한다는 점이 기억해야할 점 인것 같다.

💎 전체 코드


#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N;

int main(int argc, const char * argv[]) {
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    cin >> N;
    
    for(int i = 0;i < N;i++){
        int temp;
        cin >> temp;
        if(maxHeap.empty())
            maxHeap.push(temp);
        else{
            if(maxHeap.size() > minHeap.size())
                minHeap.push(temp);
            else
                maxHeap.push(temp);
            
            if(maxHeap.top() > minHeap.top()){
                int x = maxHeap.top();
                int y = minHeap.top();
                maxHeap.pop();
                minHeap.pop();
                maxHeap.push(y);
                minHeap.push(x);
            }
        }
        cout << maxHeap.top() << "\n";
    }
    
    return 0;
}

💎 고민


우선 순위 큐를 이용하는 문제를 다시 풀어보았는데 코드의 길이는 그렇게 길지 않았지만 두 개의 우선 순위 큐를 활용해보는 좋은 문제였다. 사실 아이디어가 떠오르지 않아서 우선 순위 큐에 중간 값을 찾는 방법을 검색해보니 최대 힙과 최소 힙을 이용하여 풀 수 있다는 것을 알고 풀었다... 난 부족해 ㅠㅠ 다음 문제는 프로그래머스나 다른 언어로도 풀어볼 수 있도록 해봐야할 것 같다,,,백준 이외에 코딩 테스트 문제도 직접 풀어보자!!

화이팅!!
아참 즐거운 설날 보내세요~~!

profile
안녕하세욤

0개의 댓글