본문 바로가기
알고리즘 문제 풀이/백준

백준 1655 가운데를 말해요 c++

by 옹구스투스 2021. 3. 23.
반응형

문제 출처 : https://www.acmicpc.net/problem/1655

 

1655번: 가운데를 말해요

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

www.acmicpc.net

 

문제

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

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

출처

  • 문제를 각색한 사람: baekjoon
  • 문제를 만든 사람: ntopia
  • 데이터를 추가한 사람: pichulia

알고리즘 분류

보기

시간 제한

  • Python 3: 0.6 초
  • PyPy3: 0.6 초
  • Python 2: 0.6 초
  • PyPy2: 0.6 초

풀이

우선순위 큐 하나로 큐의 사이즈를 2로 나눈 몫만큼 top,pop하는 방식으로 제출했으나
시간 초과..
곰곰이 생각해 보다가 안돼서 결국 구글링

참고 : https://www.crocus.co.kr/625

백준 문제를 풀면서 이 분의 풀이를 가장 많이 참고한 것 같다.
뭐 하시는 분일까

무튼 핵심은
우선순위 큐를 2개를 선언한다
1.max 큐
2.min 큐
max 큐의 top에는 작은 값들 중에 최댓값이 들어간다.
min 큐의 top에는 큰 값들 중에 최솟값이 들어간다.

만약 max큐의 top값이 min큐의 top값 보다 클 시,
max큐와 min큐의 top 값을 swap 해줘서 max 큐의 top 값에
전체수가 짝수일 시 작은 수를 출력,
전체수가 홀수일 시 중간 값을 출력 조건을 맞춰준다.

시간초과 코드

#include<iostream>
#include<queue>

using namespace std;

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

    int t;
    cin >> t;
    priority_queue<int> pq;

    while (t--) {
        int a,size;
        cin >> a;
        pq.push(a);
        size = pq.size()/2;
        if (size < 1) {
            cout << pq.top() << '\n';
        }
        else {
            vector<int> vec;
            for (int i = 0; i < size; i++) {
                vec.push_back(pq.top());
                pq.pop();
            }
            cout << pq.top() << '\n';
            for (int i = 0; i < vec.size(); i++) {
                pq.push(vec[i]);
            }
        }
    }



    return 0;
}

통과 코드

#include<iostream>
#include<queue>

using namespace std;

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

    int t;
    cin >> t;
    priority_queue<int> max; //작은것들의 max값이 top
    priority_queue<int,vector<int>,greater<int>> min; //큰것들의 min값이 top

    while (t--) {
        int a, size;
        cin >> a;
        if (max.size() == min.size()) {
            max.push(a);
        }
        else {
            min.push(a);
        }
        if (!max.empty()&&!min.empty()&&max.top()>min.top()) {
            int max_val, min_val;
            max_val = max.top();
            min_val = min.top();
            max.pop();
            min.pop();
            max.push(min_val);
            min.push(max_val);


        }
        cout << max.top() << '\n';
    }



    return 0;
}
반응형

댓글