[백준][C++] 1665번 - 가운데를 말해요

짜짠!

 

이 블로그에 알고리즘 관련 포스팅은 한번도 안써봤는데

지금 새벽 3시가 넘었는데 잠도 안오고해서.. 

 

심심해서 그냥 깃허브 개인 레파지토리에 해설 파일을 정리해서 올렸는데 블로그에도 올려두면 좋을 것 같아서 포스팅을 하게 되었다.

 

요즘 알고리즘 공부를 조금씩 해보고 있는데, 기초적인 자료구조 내용은 이제 거의 다 학습한 것 같다(아마두..)

이제 알고리즘 내용을 하나씩 뜯어보기에 앞서, 자료구조 관련 문제를 하나 풀고 넘어가기로 했다.

 

---

문제 - 백준 1665번

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

문제 풀이

문제 풀이에 앞서 사실 이 풀이 내용은 그냥 내가 보려고 깃허브에 주절주절 기록해둔 거라서 두서도 없고 이해하기 난해할 수도 있다 ..
그냥 이렇게 생각할 수도 있구나 하고 가볍게 넘어가주세요..🥹

---

✔️ 문제 풀이 접근 과정

• 1655번 문제에 처음 접근했을 때, 값을 넣을 때마다 바로바로 정렬 이 이뤄져야 하기 때문에 힙을 사용해야한다는 점은 쉽게 파악할 수 있었다.
  
  
• 그런데 힙을 사용하는 순간부터 인덱스로 값에 접근할 수 없기 때문에, 이 부분을 어떻게 처리해야할지 고민해야했다.
  
  
• 처음에는 그냥 단순히 힙과 덱(혹은 스택) 을 함께 사용하는 방법을 생각했다.
  • 1️⃣ 값이 들어올 때마다 최소힙에 push
    2️⃣ 최소힙 크기의 절반 만큼의 숫자들을 pop해서 덱에다가 push
    3️⃣ 최소힙의 top 출력
    4️⃣ 덱에 저장된 값들을 다시 최소힙에 넣는다
    5️⃣ 위 과정 반복
  • 그런데 이 풀이를 자세히 보면, 결국에는 n번의 연산이 이루어지고 있다. ( n / 2 번 pop + n / 2 번 push = n 번 )
    이미 값을 입력받으면서 n번의 for문을 돌린 상태에서, for문 내부적으로 n번의 연산을 수행하고 있으므로, 이 풀이는 시간초과가 뜰 것이다.
• 이후로도 힙은 일단 무조건 써야하긴 하는데, 중간값을 어떻게 산출해야할지 를 계속 고민했다.
  그러다가 입력받은 값들을 두 가지 저장소에 따로 저장하는 아이디어가 떠올랐다.
  힙을 사용하긴 해야하는데, 앞에서 설명한 방법은 시간초과가 뜨니까.. 여기서 다시 떠올린 방법은 중간값을 기준으로 작은 숫자가 모인 힙, 큰 숫자가 모인 힙으로 나눠서 값을 저장하는 것이다.
  
  
• 나는 설계 과정에서 작은 숫자들이 모인 힙의 가장 큰 값이 중간값이 되도록 설계했다.
  즉, 작은 숫자들이 모인 힙은 최대힙이 되어야 한다.
  
  예시 ) 3 1 5 2 4 입력
  1️⃣ 3 입력
  작은 숫자 힙 👉🏻 3
  큰 숫자 힙 👉🏻
  ∵ 작은 숫자 힙의 top == 3 (중간값)
  
  ... 중간 과정 생략 ...
  
  4️⃣ 2 입력
  작은 숫자 힙 👉🏻 1 2
  큰 숫자 힙 👉🏻 3 5
  ∵ 작은 숫자 힙의 top == 2 (중간값)
  
  5️⃣ 4 입력
  작은 숫자 힙 👉🏻 1 2 3
  큰 숫자 힙 👉🏻 4 5
  
  ∵ 작은 숫자 힙의 top == 3 (중간값)
  
  
• 이제 값을 입력할 때마다 작은 숫자 힙과 큰 숫자 힙이 위의 형태를 계속 유지하도록 코드를 짜면 된다.

 

✏️ 코드 작성하기

접근 방식은 떠올렸지만 이를 코드로 구현하기가 생각보다 쉽지 않았다.

항상 작은 숫자 힙에는 작은 숫자들이 저장되어야하고, 큰 숫자 힙에는 큰 숫자들이 저장되어야 한다.
짝수번째 입력에서는 작은 숫자 힙의 size는 큰 숫자 힙의 size와 같아야 한다.
홀수번째 입력에서는 작은 숫자 힙의 size가 큰 숫자 힙의 size보다 1만큼 커야한다.

위 조건들이 항상 성립되도록 경우를 다 따져서 설계를 해주어야했기 때문에, 생각보다 코드를 짜는게 쉽지 않았다.

 

0️⃣ 기본 세팅

#include <iostream>
#include <queue>

using namespace std;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

    priority_queue<int> pq_smaller; // 작은부분 -> 최대힙
    priority_queue<int, vector<int>, greater<int>> pq_bigger; // 큰부분 -> 최소힙

    int input_num; // 입력받은 숫자를 저장할 변수

    for (int i = 1; i <= n; ++i) {
        cin >> input_num;
    }

    return 0;
}

1️⃣ pq_smaller 와 pq_bigger 영역 나누기

일단 초기에 pq_smaller 영역과 pq_bigger 영역을 명확하게 나눠야한다.
이는 값이 최소 두 개는 들어와야 결정할 수 있다.

ex)
첫 번째 입력 :: 5 ➡️ 일단 pq_smaller에 넣기
두 번째 입력 :: 1 ➡️ 1이 pq_smaller에 들어가야 하고, 5는 pq_bigger에 들어가야 한다.

따라서 초기에 두 영역을 나누는 코드를 먼저 작성했다.

#include <iostream>
#include <queue>

using namespace std;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

    priority_queue<int> pq_smaller; // 작은부분 -> 최대힙
    priority_queue<int, vector<int>, greater<int>> pq_bigger; // 큰부분 -> 최소힙

    int input_num; // 입력받은 숫자를 저장할 변수

    for (int i = 1; i <= n; ++i) {
        cin >> input_num;

        // * 영역 나누기 :: pq_bigger, pq_smaller 결정하기
        // ? pq_bigger, pq_smaller 내부 요소 집합은 요소가 2개 이상일 때부터 결정 가능
        if (i == 1) {
            // 처음 값은 일단 무조건 smaller에 넣기
            pq_smaller.push(input_num);
        } else if (i == 2) { // 두 번째 값이 입력되었을 때
            // 입력값이 smaller에 있는 값보다 크면, bigger에 push
            if (pq_smaller.top() < input_num) {
                pq_bigger.push(input_num);
            // 입력값이 smaller에 있는 값보다 작으면, 자리를 바꿔야함
            } else {
                pq_bigger.push(pq_smaller.top());
                pq_smaller.pop();
                pq_smaller.push(input_num);
            }
        }
    }

    return 0;
}

2️⃣ 입력 값의 위치 결정하기

앞에서 두 번째 값이 입력될 때, 두 영역을 명확히 나눠놓았다.
따라서 그 이후에 입력되는 값들은 값의 크기에 따라 위치만 잘 결정해서 푸시하면 된다.

#include <iostream>
#include <queue>

using namespace std;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

    priority_queue<int, vector<int>, greater<int>> pq_bigger; // 큰부분 -> 최소힙
    priority_queue<int> pq_smaller; // 작은부분 -> 최대힙
    int input_num;

    for (int i = 1; i <= n; ++i) {
        cin >> input_num;

        if (i == 1) {
            pq_smaller.push(input_num);
        } else if (i == 2) {
            if (pq_smaller.top() < input_num) {
                pq_bigger.push(input_num);
            } else {
                pq_bigger.push(pq_smaller.top());
                pq_smaller.pop();
                pq_smaller.push(input_num);
            }
        }

        // * pq_bigger과 pq_smaller가 결정된 상태일 때 - 입력받은 숫자를 적절한 위치에 push

        // 입력값이 pq_bigger의 최소값보다 작으면 smaller에 푸시
        else if (input_num < pq_bigger.top()) {
            pq_smaller.push(input_num);
        }
        // 입력값이 pq_bigger의 최소값보다 크면 bigger에 푸시
        else {
            pq_bigger.push(input_num);
        }
    }

    return 0;
}

3️⃣ 중간값 결정하기

이때, 바로 smaller의 top을 출력하면 안된다. 바로 예외처리가 안되어있기 때문이다.
여태 짠 코드에서는 pq_smaller의 top 값이 무조건 중간값이라는 보장을 할 수 없다.

1️⃣ pq_smaller의 사이즈가 pq_bigger의 사이즈보다 1만큼 크거나 (홀수개가 입력되었을 때),
2️⃣ pq_smaller의 사이즈와 pq_bigger의 사이즈가 서로 같을 때 (짝수개가 입력되었을 때) 만
pq_smaller의 top이 중간값이라고 보장할 수 있기 때문이다.

따라서 앞 과정에서 값의 위치를 잘 결정해주었다면, 이제는 각 영역의 size를 우리가 원하는 조건대로 맞춰주면 된다.

#include <iostream>
#include <queue>

using namespace std;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

    priority_queue<int, vector<int>, greater<int>> pq_bigger; // 큰부분 -> 최소힙
    priority_queue<int> pq_smaller; // 작은부분 -> 최대힙
    int input_num;

    for (int i = 1; i <= n; ++i) {
        cin >> input_num;

        if (i == 1) {
            pq_smaller.push(input_num);
        } else if (i == 2) {
            if (pq_smaller.top() < input_num) {
                pq_bigger.push(input_num);
            } else {
                pq_bigger.push(pq_smaller.top());
                pq_smaller.pop();
                pq_smaller.push(input_num);
            }
        } else if (input_num < pq_bigger.top()) {
            pq_smaller.push(input_num);
        } else {
            pq_bigger.push(input_num);
        }

        // * 가운데 위치한 숫자 찾기

        // smaller가 bigger보다 작을 때 -> bigger에 있는 요소를 smaller에 옮겨주어야 한다
        if (pq_smaller.size() < pq_bigger.size()) {
            pq_smaller.push(pq_bigger.top());
            pq_bigger.pop();
        // smaller의 size와 bigger의 size 차가 1보다 클 때 -> smaller의 요소를 bigger로 옮겨야 한다
        } else if (pq_smaller.size() - pq_bigger.size() > 1) {
            pq_bigger.push(pq_smaller.top());
            pq_smaller.pop();
        }

        // 중간 값인 smaller의 top을 출력
        cout << pq_smaller.top() << '\n';
    }

    return 0;
}

 

---

반례를 하나씩 떠올리면서 예외처리 코드를 추가하다보니 코드가 많이 복잡해진 느낌이다. 분명히 더 좋은 풀이 방법이 있을 것 같은데, 일단 이번에 작성한 풀이 과정을 적어두면 도움이 되지 않을까 싶어서 기록해두었다.

그냥 이렇게 풀 수도 있구나 하고 넘어가자..!