[백준 2243] 사탕상자

▪︎ 문제

---

백준 2243 문제

▪︎ 알고리즘 설계

---

• 명령어 1: 사탕 꺼내기, 맛의 순위 선택, 개수 무조건 1개, 꺼내는 사탕 출력
• 명령어 2: 사탕 넣기 or 꺼내기(+ / -), 맛의 순위 선택, 개수 정할 수 있음
• 예시로 이해하기
  • 2 1 2 : 1위 맛 사탕 2개 넣기 (현재 사탕 개수: 1위 - 2개)
  • 2 3 3 : 3위 맛 사탕 3개 넣기 (현재 사탕 개수: 1위 - 2개, 3위 - 3개)
  • 1 2 : 2등 맛 사탕 1개 꺼내기 (현재 사탕 개수: 1위 - 1개, 3위 - 3개) → 1 출력
  • 1 2 : 2등 맛 사탕 1개 꺼내기 (현재 사탕 개수: 1위 - 1개, 3위 - 2개) → 3 출력
  • 2 1 -1 : 1등 맛 사탕 1개 꺼내기 (현재 사탕 개수: 3위 - 2개)
  • 1 2 : 2등 맛 사탕 1개 꺼내기 (현재 사탕 개수: 3위 - 1개) → 3 출력

▪︎ 코드

---

import java.io.*;
import java.util.*;

public class Main {

    static final int MAX = 1_000_000;
    static long[] tree = new long[MAX * 4];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); // 수정이가 사탕상자에 손을 댄 횟수

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken()); // 명령문

            if (A == 1) { // 사탕 상자에서 사탕을 꺼내는 경우(개수: 1개)
                long B = Long.parseLong(st.nextToken()); // 꺼낼 사탕의 맛 순위
                long flavor = findCandy(1, 1, MAX, B); // B번째 사탕 맛 찾기
                bw.write(flavor + "\n");
                update(1, 1, MAX, flavor, -1); // 사탕 1개 감소
            }
            
            else if (A == 2) { // 사탕 상자에 사탕을 넣는 경우
                long B = Long.parseLong(st.nextToken()); // 넣을 사탕의 맛 순위
                long C = Long.parseLong(st.nextToken()); // 넣을 사탕의 개수(양수: 넣는 경우, 음수: 빼는 경우)
            
                update(1, 1, MAX, B, C); // 맛 B 사탕 개수 C만큼 변경
            }  
        }

        bw.flush();
    }
    
    // 트리 업데이트 (사탕 + 또는 -)
    static void update(int node, int start, int end, long idx, long diff) {
        if (idx < start || idx > end) return; // 범위 벗어나면 종료
        tree[node] += diff; // 사탕 값 변경
            
        if (start != end) { // 리프 노드가 아니라면 자식 호출
            int mid = (start + end) / 2;
            update(node * 2, start, mid, idx, diff);
            update(node * 2 + 1, mid + 1, end, idx, diff);
        }
    }

    // B번째 사탕 찾기
    static int findCandy(int node, int start, int end, long rank) {
        if (start == end) return start;  // 리프 도착 -> 맛 순위 반환
            
        int mid = (start + end) / 2;
    
        if (tree[node * 2] >= rank) {
            return findCandy(node * 2, start, mid, rank);
        } else {
            return findCandy(node * 2 + 1, mid + 1, end, rank - tree[node * 2]);
            // 왼쪽 자식 노드 건너뛰고 오른쪽 자식노드 순위 계산 (위치에 따른 순위 탐색)
        }
    }
}

▪︎ 시간복잡도

---

O(log N)

▪︎ 틀린 이유

---

• 자료구조 선택 부적합
  • 이 문제는 B번째 사탕을 빠르게 찾는 기능이 핵심
  • LinkedList는 순위 기반 탐색에 적합하지 않음 (트리를 써야 함)
• 세그먼트 트리 배열 크기 잘못 설정
  • tree = new int[n * 4]; → n은 명령 횟수, 맛 순위 최대값이 아님
  • 올바른 크기: tree = new long[MAX * 4];
  • 이 오류로 인해 트리 탐색 시 배열 인덱스 초과 런타임 에러 발생
• 트리에 저장해야 할 값에 대한 혼동
  • 트리의 값이 순위인지 헷갈림 → 실제로는 해당 구간의 사탕 개수 합이 저장됨
  • rank는 단순히 찾는 순서 기준 값이고, 트리에는 각 구간의 합만 저장
• rank에서 왼쪽 트리 개수를 빼는 이유를 이해 못함
  • 처음에는 rank 감소가 직관적으로 보이지 않았음
  • 실제로는 왼쪽 구간의 사탕 개수를 건너뛰었기 때문에 오른쪽에서는 새로운 기준 rank가 필요함
• 재귀 동작 구조 이해 부족
  • update는 idx가 포함된 구간만 갱신해야 O(logN)
  • findCandy는 왼쪽 → 오른쪽 순으로 rank를 줄이며 탐색하는 이진 탐색적 로직

▪︎ 느낀점 / 기억할 정보

---

• 순위 기반 선택 문제 → 세그먼트 트리를 통해 해결 가능
• 세그먼트 트리의 핵심 개념
  • 트리의 각 노드는 구간 [start~end]의 사탕 개수 합을 저장
  • 리프 노드 [i~i]는 맛 i 사탕 개수를 저장
• findCandy()의 동작 원리
  • rank는 몇 번째 사탕인지를 의미
  • 왼쪽 자식의 개수 >= rank → 왼쪽으로 이동 (왼쪽 자식에 해당 사탕이 포함되어 있기 때문)
  • 왼쪽 자식의 개수 < rank → rank에서 왼쪽 개수를 빼고 오른쪽으로 이동 (왼쪽 자식에 해당 사탕이 포함되지 못하기 때문)
  • 리프에 도착하면 해당 맛 순위 반환
• update()의 동작 원리
  • idx가 속한 구간만 갱신
  • 해당되는 맛 순위의 리프만 바꾸고, 관련된 부모 구간의 합만 갱신 (부모 → 자식 값 갱신 가능, 재귀 이용)
  • 구간에 포함되지 않으면 return
  • 포함되면 현재 노드 값 갱신 후, 왼쪽/오른쪽 자식으로 재귀
• 트리의 구조
  • 세그먼트 트리를 트리 전체를 재정렬하지 않아도 됨
  • 구간 [1~N]을 mid 기준으로 [1~mid], [mid+1~N]으로 분할
  • 사탕맛 순위를 인덱스로 사용함
  • 왼쪽 리프부터 순위가 높음 (작은 인덱스를 먼저 탐색하기 때문!)
• B번째 사탕을 찾는 과정
  • rank는 왼쪽 트리의 개수를 건너뛸 때마다 감소
  • 따라서 rank 감소는 오른쪽에서 새 기준으로 순위를 다시 세는 것