쌉쌀한 무화과의 개발로그

[문제]

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

각각의 사탕은 그 맛의 좋고 나쁨이 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인 모든 입력에 대해서, 꺼낼 사탕의 맛의 번호를 출력한다. 물론, A=2 이면서 C<0 일 때는 출력하지 않는다.

​

[예제]

>문제 이해

설명)) 사탕의 맛은 좋고 나쁨이 1~ 1,000,000의 정수로 구분된다.

= 나쁨수치 (숫자가 작을수록 맛있고, 높을수록 맛없음)

​

input))

N: 수정이가 사탕상자에 손을 댄 횟수

N개의 줄에는) A, B 또는 A, B, C가 주어진다.

​

1) A==1이면? 상자에서 사탕 꺼내는

B=꺼낼 사탕의 순위

2) A==2이면? 사탕을 넣는 경우

B=넣을 사탕의 맛

C=사탕 개수 (음수면 뺄셈)

​

사탕의 총 개수는 2,000,000,000을 넘지 않는다.

잘못된 입력은 주어지지 않는다.

​

output))

A가 1인 모든 입력에 대해: 꺼낼 사탕의 맛의번호 출력

A가 2이면서 C<0이면 출력X

​

​

>문제 풀이

1. 인덱스의 따른 값이 계속해서 바뀐다.

2. 순위 정보가 필요한데 값이 계속 바뀐다. 범위값이 백만이라 누적합을 매번 구한다면 시간초과가 남.

=> 인덱스 트리를 사용한다.

​

그래서 포화 이진 트리를 만들어야 하는데, 백만 이상의 2의 제곱수 만큼의 트리를 만들어야한다.

​

왜냐면, 위처럼 포화 이진 트리를 만들 때, 만약 리프노드가 8개이면 총 15개의 공간이 필요한데, 노드의 번호를 편하게 쓰려면 0을 제외하고 15개의 공간을 만들어야함. 즉 2*leaf=16 공간이 필요하게된다.

​

이 문제에서는 사탕의 맛의 정도가 1~1,000,000 라서 리프 노드만 백만개이다.

트리를 만들 때는 완전 이진 트리를 만들어야 계산할 수 있으므로 백만이 넘는 2의 제곱수가 필요하다.

​

* 트리 구조에서 부모노드와 자식노드의 번호의 관계

parent= left/2 (또는 right/2);

left= parent*2;

right= parent*2+1;

>전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
	static int tree[];
	static int N, S, A, B, C;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
        //포화 이진트리 생성을 위한 2^n>1000000인 S(=2^n) 찾기
		S=1;
		while(S<1000000) {
			S*=2;
		}
		tree= new int[S*2];
		
		N= Integer.parseInt(br.readLine());
		StringBuilder sb= new StringBuilder();
		for(int i=0; i<N; i++) {
			st= new StringTokenizer(br.readLine());
			A= Integer.parseInt(st.nextToken());
			if(A==1) {
				B= Integer.parseInt(st.nextToken());
				//사탕 꺼내기, B번째
				int index= pickup(1, S, 1, B);
				sb.append(index+"\n");
				update(1, S, 1, index, -1);
			}else {
				B= Integer.parseInt(st.nextToken());
				C= Integer.parseInt(st.nextToken());
				//사탕 넣기 B맛 C개(양수+, 음수-)
				update(1, S, 1, B, C);
			}
		}
		System.out.println(sb.toString());
	}//main
	
    //left, right는 범위(1~S), node: 현재 위치한 노드의 인덱스, target: 목표 노드
	public static int pickup(int left, int right, int node, int target) {
		if(left==right) return left;
		
		int mid= (left+right)/2;
		if(tree[node*2]>=target) { //왼쪽 노드이면 (target그대로)
			return pickup(left, mid, node*2, target);
		}else { //오른쪽 노드이면 (target-왼쪽 노드)
			return pickup(mid+1, right, node*2+1, target-tree[node*2]);
		}
	}
	
    //(left, right, node, target, diff: 더하거나 뺄 사탕개수)
	public static void update(int left, int right, int node, int target, int diff) {
		//타겟이 범위값 벗어나면 종료
		if(target<left||right<target) return;
		
		tree[node]+=diff;
		if(left!=right) {
			int mid= (left+right)/2;
			update(left, mid, node*2, target, diff);
			update(mid+1, right, node*2+1, target, diff);
		}
	}	
}

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