[백준] 2243번 : 사탕상자

2243번: 사탕상자

2243번: 사탕상자

🤔 문제분석

세그먼트 트리와 팬윅트리를 활용하여 문제를 해결하였습니다.

팬윅 트리

팬윅 트리로 문제를 해결 할때에는 이분탐색과 팬윅트리를 사용하여 문제를 해결하였습니다. 사탕의 순위를 누적합으로 계산시키고, 이분탐색으로 사탕을 찾아 나아 갑니다.

1. 쿼리함수의 인자는 사탕의 가치가 되고 사탕의 가치를 입력하면 현재 그 사탕의 가치의 순위가 리턴 됩니다.
2. 업데이트 함수는 사탕의 정보를 업데이트 합니다.

쿼리함수로 리턴받은 순위에 따라서 왼쪽을 탐색할 것인지, 오른쪽을 탐색할 것인지 나눕니다.

세그먼트 트리

세그먼트 트리로 문제를 해결할때에는 사탕의 순위(사탕의 가치)를 누적합으로 계산하여 찾습니다. 세그먼트 트리의 각 노드가 어떤 역할을 하는지 알고있다면, 문제를 쉽게 접근 할 수 있습니다.

예를들어 사탕의 순위 50을 찾는다고 가정한다면, 노드 1번에 위치했을때, 노드 2번을 확인합니다. 만약 노드 2번이 50보다 작은 값을 가지고 있다면 노드 2번을 재귀호출합니다. 50보다 클경우는 3번 노드를 재귀호출 합니다.

이런식으로 재귀호출하여 문제를 해결합니다. 여기서 구간을 반반으로 나누어 가면서 조건에 따라서 재귀 호출 합니다.

쿼리를 해가면서 리프노드에 도달하면 그 리프노드는 바로 사탕의 가치 값 입니다.

📝 의사코드

팬윅 트리

1. 사탕을 업데이트 하거나, 사탕의 순위를 출력하고 업데이트합니다.
   1. 사탕의 순위를 구하는 로직
      1. mid 값으로 사탕의 가치를 넣으면, 현재 사탕의 가치가 순위가 몇인지 나온다.
      2. 현재사탕의 가치가 찾는 순위보다 클경우 왼쪽을 탐색한다. ( end = mid )
      3. 현재사탕의 가치가 찾는 순위보다 작을경우 오른쪽을 탐색한다. ( start = mid + 1 )

세그먼트 트리

1. 사탕을 업데이트 하거나, 사탕의 순위를 출력하고 업데이트합니다.
   1. 사탕의 순위를 구하는 로직
      1. node*2 왼쪽노드를 확인한다.
      2. 왼쪽 노드값이 사탕의 순위보다 클경우 왼쪽을 탐색한다. ( node*2 를 재귀 호출 )
      3. 왼쪽 노드값이 사탕의 순위보다 작을경우 오른쪽 노드를 탐색한다. ( node*2+1를 재귀호출 )
      4. start == end 가 될겨우 ( 리프노드에 도달했을경우 ) 현재 인덱스를 반환한다.

💻 코드

팬윅 트리

import sys
input = sys.stdin.readline
CANDY_CNT = 1000001

N = int(input())
fwt = [0 for _ in range(CANDY_CNT+1)]

def update(candy, cnt):
    idx = candy
    while idx <= CANDY_CNT:
        fwt[idx] += cnt
        idx += (idx&-idx)

def query(idx):
    cnt = 0
    while idx >= 1:
        cnt += fwt[idx]
        idx -= (idx&-idx)
    
    return cnt

def find(cnt):
    start = 1
    end = CANDY_CNT
    while start < end:
        mid = (start+end) // 2
        rank = query(mid)
        if rank >= cnt:
            end = mid
        else:
            start = mid + 1
    return end

for _ in range(N):
    temp = list(map(int, input().split()))
    if temp[0] == 2:
        B, C = temp[1:]
        update(B, C)
    else:
        B = temp[-1]
        candy = find(B)
        print(candy)
        update(candy, -1)

세그먼트 트리

import sys
input = sys.stdin.readline
CANDY_CNT = 1000001

N = int(input())
tree = [0 for _ in range(CANDY_CNT*4)]

def update(start, end, node, idx, value):
    if idx < start or idx > end:
        return
    
    if start == end:
        tree[node] += value
        return
    
    mid = (start+end)//2
    update(start, mid, node*2, idx, value)
    update(mid+1, end, node*2+1, idx, value)
    
    tree[node] = tree[node*2] + tree[node*2+1]
    
def query(start, end, node, cnt):
    if start == end:
        return end
    
    mid = (start+end)//2
    cur_cnt = tree[node*2]
    if cur_cnt >= cnt:
        return query(start, mid, node*2, cnt)
    else:
        return query(mid+1, end, node*2+1, cnt - cur_cnt) 
    

for _ in range(N):
    temp = list(map(int, input().split()))
    if temp[0] == 2:
        B, C = temp[1:]
        update(0, CANDY_CNT, 1, B, C)
    else:
        B = temp[-1]
        candy = query(0, CANDY_CNT, 1, B)
        print(candy)
        update(0, CANDY_CNT, 1, candy, -1)

🎯 피드백 및 개선사항

세그먼트 트리의 성질을 다시한번더 생각 해 볼 수 있게 되었습니다. 세그먼트 트리는 이분탐색을 기반이기 때문에 이분탐색 성질에 대해서도 다시한번더 생각해 볼 수 있었습니다.

❓다른사람은 어떻게 풀었을까

세그먼트 트리와 팬윅트리를 사용하여 이분탐색으로 문제를 접근 하였습니다.