[BOJ/Platinum 5] 백준 2243 사탕상자(C++)

문제 링크

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

2243번: 사탕상자

 

문제

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

각각의 사탕은 그 맛의 좋고 나쁨이 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인 모든 입력에 대해서, 꺼낼 사탕의 맛의 번호를 출력한다.

예제 입력 1

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

예제 출력 1

1
3
3

알고리즘 분류

• 자료 구조

풀이

세그먼트 트리에 특정 맛 사탕의 개수를 저장하고 꺼내면서 수정이가 꺼낸 사탕의 맛을 알 수 있다.

우선 A가 2라면, C의 부호에 따라 사탕을 넣을 지, 아니면 꺼낼 지가 달라진다. 

MAP[B] += C;
Update_SegTree(1, 1, 1000000, B, C);

A가 1이라면 무조건 하나를 꺼내 오는 것이기 때문에 B순위의 사탕에 -1을 해준다.

int Candy = Find_Value(1, 1, 1000000, B);
MAP[Candy]--;
Update_SegTree(1, 1, 1000000, Candy, -1);

Find_Value() 함수를 통해 B순위인 사탕의 맛이 무엇인지를 확인하고, 해당 맛 사탕의 개수를 1 감소시키고 세그먼트 트리 역시 업데이트해준다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1000001
#define LL long long
#define INF 1e9

using namespace std;
struct INFO {
	int A, B, C;
};

int N;
vector<INFO> Query;
int MAP[MAX];
vector<int> SegTree;

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int A, B;
		cin >> A >> B;
		if (A == 1) {
			Query.push_back({ A,B,0 });
		}
		else if (A == 2) {
			int C;
			cin >> C;
			Query.push_back({ A,B,C });
		}
	}
}

void Update_SegTree(int Node, int S, int E, int Val, int Diff) {
	if (S == E) {
		SegTree[Node] += Diff;
		return;
	}
	int M = (S + E) / 2;
	if (Val <= M) {
		Update_SegTree(Node * 2, S, M, Val, Diff);
	}
	else {
		Update_SegTree(Node * 2 + 1, M + 1, E, Val, Diff);
	}
	SegTree[Node] = SegTree[Node * 2] + SegTree[Node * 2 + 1];
}

int Find_Value(int Node, int S, int E, int Val) {
	if (S == E) {
		return S;
	}
	int M = (S + E) / 2;
	if (Val <= SegTree[Node * 2]) {
		return Find_Value(Node * 2, S, M, Val);
	}
	else {
		return Find_Value(Node * 2 + 1, M + 1, E, Val - SegTree[Node * 2]);
	}
}

void Settings() {
	int Tree_Height = (int)ceil(log2(1000000));
	int Tree_Size = (1 << (Tree_Height + 1));
	SegTree.resize(Tree_Size);
}

void Find_Answer() {
	for (int i = 0; i < Query.size(); i++) {
		int A = Query[i].A;
		int B = Query[i].B;
		int C = Query[i].C;
		if (A == 1) {
			int Candy = Find_Value(1, 1, 1000000, B);
			cout << Candy << "\n";
			MAP[Candy]--;
			Update_SegTree(1, 1, 1000000, Candy, -1);
		}
		else if (A == 2) {
			MAP[B] += C;
			Update_SegTree(1, 1, 1000000, B, C);
		}
	}
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}