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

2022. 11. 19. 03:43·algorithm

짜짠!

 

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

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

 

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

 

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

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

 


문제 - 백준 1665번

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

 

1655번: 가운데를 말해요

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

www.acmicpc.net

 

문제 풀이

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

✔️ 문제 풀이 접근 과정

  • 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;
}
 


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

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

 

 

'algorithm' 카테고리의 다른 글

[백준][C++] 11000번 - 강의실 배정  (0) 2022.12.25
'algorithm' 카테고리의 다른 글
  • [백준][C++] 11000번 - 강의실 배정
민똔
민똔
  • 민똔
    기록은 기억보다 오래 머무른다
    민똔
  • 전체
    오늘
    어제
    • All (24)
      • web (1)
      • frontend (12)
        • javascript (8)
        • CSS (1)
        • react (2)
      • backend (3)
        • CS (1)
        • java (1)
        • spring (1)
      • algorithm (2)
      • 우아한테크코스 7기 (6)
        • 회고 (6)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

    • 깃허브
  • 공지사항

  • 인기 글

  • 태그

    리팩토링
    batchsize
    백준 11000
    css
    그리디 알고리즘
    Java
    SUBSELECT
    JWT
    백준
    secure cookie
    개방 폐쇄 원칙
    httpOnly cookie
    spring
    일급 컬렉션
    fetch join
    Local Storage
    access token
    LSP
    Refresh Token
    cookies
    개발
    로그인 기능 구현
    Session Storage
    객체지향
    SOLID
    OCP
    Session
    N+1 문제
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
민똔
[백준][C++] 1665번 - 가운데를 말해요
상단으로

티스토리툴바