[백준] 2243 - 사탕상자 (Java)

문제

수정이는 어린 동생을 달래기 위해서 사탕을 사용한다. 수정이는 평소에 여러 개의 사탕을 사서 사탕상자에 넣어두고, 동생이 말을 잘 들을 때면 그 안에서 사탕을 꺼내서 주곤 한다.

각각의 사탕은 그 맛의 좋고 나쁨이 1부터 1,000,000까지의 정수로 구분된다. 1이 가장 맛있는 사탕을 의미하며, 1,000,000은 가장 맛없는 사탕을 의미한다. 수정이는 동생이 말을 잘 들은 정도에 따라서, 사탕상자 안에 있는 사탕들 중 몇 번째로 맛있는 사탕을 꺼내주곤 한다. 예를 들어 말을 매우 잘 들었을 때에는 사탕상자에서 가장 맛있는 사탕을 꺼내주고, 말을 조금 잘 들었을 때에는 사탕상자에서 여섯 번째로 맛있는 사탕을 꺼내주는 식이다.

수정이가 보관하고 있는 사탕은 매우 많기 때문에 매번 사탕상자를 뒤져서 꺼낼 사탕을 골라내는 일은 매우 어렵다. 수정이를 도와주는 프로그램을 작성하시오.

---

입력

첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. 이때에는 한 정수만 주어지며, B는 꺼낼 사탕의 순위를 의미한다. 이 경우 사탕상자에서 한 개의 사탕이 꺼내지게 된다. 또, A가 2인 경우는 사탕을 넣는 경우이다. 이때에는 두 정수가 주어지는데, B는 넣을 사탕의 맛을 나타내는 정수이고 C는 그러한 사탕의 개수이다. C가 양수일 경우에는 사탕을 넣는 경우이고, 음수일 경우에는 빼는 경우이다. 맨 처음에는 빈 사탕상자에서 시작한다고 가정하며, 사탕의 총 개수는 2,000,000,000을 넘지 않는다. 또한 없는 사탕을 꺼내는 경우와 같은 잘못된 입력은 주어지지 않는다.

출력

A가 1인 모든 입력에 대해서, 꺼낼 사탕의 맛의 번호를 출력한다.

---

예제 입력

6
2 1 2
2 3 3
1 2
1 2
2 1 -1
1 2

예제 출력

1
3
3

---

해결 방법

Tree[ ] 에는 (start ~ end) 범위에 속하는 맛을 가진 사탕들의 총합을 기록합니다. 

 

[ update ]

차이값으로 업데이트 하는 방식입니다. 

 

[ query ]

mid = (start + end) / 2

mid 기준으로 왼쪽 자식이 맛있는 쪽을 다루고 있습니다. 

 

찾으려는 순위의 수(k) 가 tree[왼쪽자식] 보다 작다면 왼쪽 자식의 범위 내에 우리가 찾으려는 인덱스가 있는 것이므로

-> query(왼쪽 자식 노드, 0, mid, k)를 호출

 

찾으려는 순위가 tree[왼쪽 자식] 보다 크다면 오른쪽 자식이 다루는 범위 안에 있다는 의미이므로

오른쪽 자식에서 (k - tree[왼쪽자식])번째 순위를 찾아야 합니다. 

-> query (오른쪽 자식 노드, mid + 1, end, k)

 

코드

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

public class Main {
	
	public static class SegmentTree {
		// 맛의 강도 범위
		long[] tree;
		int n;
		
		SegmentTree() {
			n = 1_000_001;
			tree = new long[4*n];
		}
		
		public void update(int b, long c) {
			updateHelper(1, 0, n-1, b, c);
		}
		
		private  void updateHelper(int node, int start, int end, int b, long c) {
			
			if (b < start || b > end) return;
			
			tree[node] += c;
			
			if (start != end) {
				int mid = (start + end) / 2;
				updateHelper(node * 2, start, mid, b, c);
				updateHelper(node * 2 + 1, mid + 1, end, b, c);
			}
		}
		
		public int query(int b) {
			return queryHelper(1, 0, n-1, b);
		}
		
		private int queryHelper(int node, int start, int end, long b) {
			if (start == end) {
				return start;
			}
			
			int mid = (start + end) / 2;
			
			// 맛이 더 좋은 쪽
			long leftCount = tree[node * 2];
			
			if ( b <= leftCount ) {
				return queryHelper(node * 2, start, mid, b);
			}
			else {
				return queryHelper(node * 2 + 1, mid + 1, end, b - leftCount);
			}
			
		}
		
		
	}
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		SegmentTree segTree = new SegmentTree();
		
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			
			// 꺼내기
			if (a == 1) {
				int b = Integer.parseInt(st.nextToken());
				int idx = segTree.query(b);
				sb.append(idx).append("\n");
				segTree.update(idx, -1);
			}
			// 넣기
			else if (a == 2) {
				int b = Integer.parseInt(st.nextToken());
				long c = Long.parseLong(st.nextToken());
				
				segTree.update(b,  c);
			}
		}
		
		System.out.print(sb);
	}
}