[Baekjoon] 2243 – 사탕상자

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

📖 문제 해석하기

이 문제는 동적으로 변화하는 사탕상자에서 순위 기반 조회를 효율적으로 수행하는 문제입니다. 수정이는 사탕상자에 사탕을 넣거나 빼면서, 동시에 “몇 번째로 맛있는 사탕”을 꺼내야 합니다.

구체적으로 살펴보면, 각 사탕은 1부터 1,000,000까지의 맛 점수를 가지며(1이 가장 맛있음), 우리는 다음 두 가지 연산을 처리해야 합니다:

  • 삽입/삭제: 특정 맛의 사탕을 여러 개 넣거나 빼기
  • 순위 조회: 현재 사탕상자에서 k번째로 맛있는 사탕의 맛 점수 찾기

예를 들어, 사탕상자에 맛 점수가 [3, 3, 5, 7, 7, 7]인 사탕들이 있다면, 2번째로 맛있는 사탕은 맛 점수 3이고, 5번째로 맛있는 사탕은 맛 점수 7입니다.

핵심은 사탕상자의 내용이 계속 변하는 상황에서도 빠르게 순위 조회를 수행해야 한다는 점입니다.

🧠 첫 번째 시도와 한계점

가장 직관적인 접근법은 정렬된 배열이나 리스트를 유지하는 것입니다. 사탕을 넣을 때마다 적절한 위치에 삽입하고, 빼야 할 때는 해당 원소를 제거하며, k번째 원소를 조회할 때는 단순히 인덱스로 접근하는 방식입니다.

하지만 이 방법의 치명적인 문제는 삽입과 삭제의 비효율성입니다. 정렬된 상태를 유지하려면 배열 중간에 원소를 삽입하거나 삭제할 때마다 나머지 원소들을 모두 이동시켜야 합니다. 최악의 경우 각 연산이 O(N)의 시간이 걸리며, 전체 n개의 연산을 처리하는 데 O(N²)의 시간이 필요합니다.

문제의 제약조건을 보면 n이 최대 100,000이고 사탕의 총 개수도 매우 클 수 있으므로, 이런 방식으로는 시간 초과가 불가피합니다. N = 10⁵일 때 O(N²) 알고리즘은 약 100억 번의 연산을 수행하게 되어 현실적으로 불가능합니다.

💡 핵심 아이디어: 세그먼트 트리를 활용한 순위 조회

브루트 포스 방법의 한계를 극복하려면 데이터 구조의 근본적인 관점 전환이 필요합니다. 문제를 자세히 분석해보면, 우리가 실제로 관리해야 하는 것은 개별 사탕들이 아니라 각 맛 점수별로 몇 개의 사탕이 있는지라는 빈도 정보입니다.

이 관찰에서 출발하여, 맛 점수를 인덱스로 하고 해당 점수의 사탕 개수를 값으로 하는 빈도 배열을 생각해볼 수 있습니다. 하지만 단순한 배열로는 여전히 순위 조회가 비효율적입니다. k번째 사탕을 찾으려면 배열을 처음부터 순회하면서 누적합을 계산해야 하기 때문입니다.

여기서 세그먼트 트리가 해답을 제공합니다. 세그먼트 트리를 사용하면 빈도 배열의 구간합을 효율적으로 관리할 수 있고, 더 중요하게는 이진 탐색의 원리를 활용하여 순위 조회를 O(log N) 시간에 수행할 수 있습니다.

📘 세그먼트 트리와 순위 조회
세그먼트 트리는 배열의 구간에 대한 연산(합, 최솟값, 최댓값 등)을 효율적으로 처리하는 자료구조입니다. 각 노드가 특정 구간의 정보를 저장하며, 트리 구조를 통해 업데이트와 조회를 모두 O(log N) 시간에 수행할 수 있습니다. 순위 조회의 경우, 루트에서 시작하여 각 단계에서 왼쪽 서브트리의 합을 확인하며 목표 순위가 어느 쪽에 있는지 판단하여 내려가는 방식으로 구현됩니다.

구체적인 작동 원리는 다음과 같습니다.

세그먼트 트리의 각 노드는 특정 맛 점수 구간에 해당하는 사탕들의 총 개수를 저장합니다. k번째 사탕을 찾을 때는 루트에서 시작하여, 현재 노드의 왼쪽 자식이 관리하는 구간에 있는 사탕의 개수를 확인합니다. 만약 왼쪽 구간의 사탕 개수가 k보다 크거나 같다면 k번째 사탕은 왼쪽에 있고, 그렇지 않다면 오른쪽에 있으면서 그 순위는 k - 왼쪽_구간_사탕수가 됩니다.

이 방법의 핵심은 사탕을 개별적으로 저장하지 않고 빈도 정보만 관리한다는 점입니다. 같은 맛 점수의 사탕들은 구별할 필요가 없으므로, 각 맛 점수별로 몇 개가 있는지만 알면 충분합니다.

🔍 알고리즘 상세 동작 과정

실제 예제를 통해 알고리즘의 동작을 살펴보겠습니다. 다음과 같은 연산 시퀀스가 있다고 가정해봅시다:

  1. 맛 점수 3인 사탕 2개 추가
  2. 맛 점수 5인 사탕 1개 추가
  3. 맛 점수 7인 사탕 3개 추가
  4. 2번째로 맛있는 사탕 조회
  5. 4번째로 맛있는 사탕 조회 및 제거

1-3단계: 사탕 추가 세그먼트 트리의 업데이트 연산을 통해 각 맛 점수별 사탕 개수를 관리합니다. 맛 점수 3에 2개, 맛 점수 5에 1개, 맛 점수 7에 3개를 추가하면, 전체 사탕상자에는 총 6개의 사탕이 있게 됩니다.

4단계: 2번째 사탕 조회 루트 노드(전체 구간 [1, 1,000,000])에서 시작합니다. 중간값을 500,000으로 하여 왼쪽 구간 [1, 500,000]과 오른쪽 구간 [500,001, 1,000,000]으로 나눕니다. 왼쪽 구간에는 맛 점수 3과 5의 사탕들이 있어 총 3개입니다. 2번째 사탕을 찾고 있고 왼쪽에 3개가 있으므로, 2번째 사탕은 왼쪽 구간에 있습니다.

왼쪽 구간에서 다시 이분 탐색을 진행합니다. 이 과정을 반복하여 최종적으로 맛 점수 3에 도달하게 됩니다.

5단계: 4번째 사탕 조회 및 제거 마찬가지로 루트에서 시작하여, 왼쪽 구간에 3개가 있고 4번째를 찾고 있으므로 오른쪽 구간으로 이동합니다. 이때 찾는 순위는 4 - 3 = 1이 됩니다. 오른쪽 구간에서 1번째로 맛있는 사탕을 찾으면 맛 점수 7이 나옵니다. 조회 후에는 해당 위치의 사탕 개수를 1 감소시킵니다.

💻 완전한 구현 코드

#include <bits/stdc++.h>
using namespace std;

<em>// 최대 맛 점수는 1,000,000이므로 이를 상수로 정의</em>
#define MAX_N 1000000

int N, A, B, C;
<em>// 세그먼트 트리 배열: 4*MAX_N 크기로 선언하여 충분한 공간 확보</em>
int seg[4*MAX_N];

<em>// 세그먼트 트리 업데이트 함수</em>
<em>// node: 현재 노드 번호, i: 업데이트할 인덱스, v: 추가/제거할 값</em>
<em>// L, R: 현재 노드가 담당하는 구간</em>
void update(int node, int i, int v, int L, int R) {
   <em>// 업데이트할 인덱스가 현재 구간 밖에 있으면 종료</em>
   if (i < L || i > R) return;
   
   <em>// 리프 노드에 도달했으면 값을 업데이트</em>
   if (L == R && L == i) {
      seg[node] += v;  <em>// 사탕 개수 증가/감소</em>
      return;
   }
   
   <em>// 구간을 반으로 나누어 재귀적으로 업데이트</em>
   int M = (L + R) / 2;
   update(node*2, i, v, L, M);        <em>// 왼쪽 자식 업데이트</em>
   update(node*2+1, i, v, M+1, R);   <em>// 오른쪽 자식 업데이트</em>
   
   <em>// 현재 노드의 값을 자식 노드들의 합으로 갱신</em>
   seg[node] = seg[2*node] + seg[2*node+1];
}

<em>// k번째 원소를 찾는 함수 (핵심 알고리즘)</em>
<em>// node: 현재 노드, target: 찾고자 하는 순위, L, R: 현재 구간</em>
int query(int node, int target, int L, int R) {
   <em>// 리프 노드에 도달하면 해당 맛 점수 반환</em>
   if (L == R) return L;
   
   int M = (L + R) / 2;
   int left = seg[2*node];  <em>// 왼쪽 자식의 총 사탕 개수</em>
   
   <em>// 왼쪽 구간의 사탕 개수가 target보다 작으면 오른쪽으로 이동</em>
   if (left < target) {
      <em>// 오른쪽 구간에서 (target - left)번째 원소를 찾음</em>
      return query(node*2+1, target - left, M+1, R);
   }
   <em>// 그렇지 않으면 왼쪽 구간에서 target번째 원소를 찾음</em>
   return query(node*2, target, L, M);
}

int main()
{
   <em>// 입출력 최적화</em>
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   
   <em>// 세그먼트 트리 초기화 (모든 값을 0으로)</em>
   memset(seg, 0LL, sizeof(seg));
   
   cin >> N;  <em>// 전체 연산 개수 입력</em>
   
   for (int i = 0; i < N; ++i) {
      cin >> A;  <em>// 연산 타입 입력</em>
      
      if (A == 1) {
         <em>// 사탕 꺼내기 연산</em>
         cin >> B;  <em>// B번째로 맛있는 사탕을 꺼냄</em>
         
         <em>// 세그먼트 트리에서 B번째 원소(맛 점수) 찾기</em>
         int target = query(1, B, 1, MAX_N);
         cout << target << "\n";  <em>// 맛 점수 출력</em>
         
         <em>// 해당 맛 점수의 사탕을 1개 제거</em>
         update(1, target, -1, 1, MAX_N);
      } else {
         <em>// 사탕 넣기/빼기 연산</em>
         cin >> B >> C;  <em>// B: 맛 점수, C: 개수 (양수면 추가, 음수면 제거)</em>
         
         <em>// 세그먼트 트리에서 해당 맛 점수의 사탕 개수 업데이트</em>
         update(1, B, C, 1, MAX_N);
      }
   }
   
   return 0;
}

🔁 대안적 접근법

이 문제는 평형 이진 탐색 트리(예: Red-Black Tree, AVL Tree)나 Order Statistics Tree를 사용해서도 해결할 수 있습니다. 이런 자료구조들은 각 노드에 서브트리의 크기 정보를 추가로 저장하여 순위 기반 조회를 지원합니다.

하지만 세그먼트 트리 접근법이 더 직관적이고 구현이 간단합니다. 특히 이 문제에서는 맛 점수의 범위가 고정되어 있어서 배열 기반의 세그먼트 트리가 적합합니다. 평형 트리는 일반적으로 더 복잡한 회전 연산과 균형 유지 로직이 필요하기 때문입니다.

또 다른 방법으로는 Fenwick Tree(Binary Indexed Tree)도 고려할 수 있습니다. Fenwick Tree는 세그먼트 트리보다 메모리를 적게 사용하고 구현이 더 간단하지만, 순위 조회를 위해서는 별도의 이진 탐색 로직을 구현해야 합니다.

📌 핵심 정리 및 교훈

이 문제의 핵심은 데이터를 어떻게 표현하고 관리할 것인가에 대한 관점의 전환이었습니다. 개별 사탕들을 직접 관리하려고 하면 비효율적이지만, 빈도 정보로 추상화하고 세그먼트 트리로 구간합을 관리하면 모든 연산을 O(log N) 시간에 수행할 수 있습니다.

특히 순위 조회라는 복잡해 보이는 연산이 세그먼트 트리의 이진 탐색 구조와 완벽하게 맞아떨어진다는 점이 인상적입니다. 이는 트리 구조에서 각 단계마다 절반씩 탐색 공간을 줄여나가는 분할 정복의 힘을 보여줍니다.

이 문제를 통해 얻을 수 있는 가장 중요한 교훈은, 복잡한 동적 조회 문제를 만났을 때 적절한 자료구조 선택의 중요성입니다. 세그먼트 트리는 단순한 구간합 문제뿐만 아니라 이런 고급 응용에서도 강력한 도구가 될 수 있음을 보여줍니다.

Similar Posts