2243번: 사탕상자
첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이
www.acmicpc.net
문제
수정이는 어린 동생을 달래기 위해서 사탕을 사용한다. 수정이는 평소에 여러 개의 사탕을 사서 사탕상자에 넣어두고, 동생이 말을 잘 들을 때면 그 안에서 사탕을 꺼내서 주곤 한다.
각각의 사탕은 그 맛의 좋고 나쁨이 1부터 1,000,000까지의 정수로 구분된다. 1이 가장 맛있는 사탕을 의미하며, 1,000,000은 가장 맛없는 사탕을 의미한다. 수정이는 동생이 말을 잘 들은 정도에 따라서, 사탕상자 안에 있는 사탕들 중 몇 번째로 맛있는 사탕을 꺼내주곤 한다. 예를 들어 말을 매우 잘 들었을 때에는 사탕상자에서 가장 맛있는 사탕을 꺼내주고, 말을 조금 잘 들었을 때에는 사탕상자에서 여섯 번째로 맛있는 사탕을 꺼내주는 식이다.
수정이가 보관하고 있는 사탕은 매우 많기 때문에 매번 사탕상자를 뒤져서 꺼낼 사탕을 골라내는 일은 매우 어렵다. 수정이를 도와주는 프로그램을 작성하시오.
문제 분석
문제를 먼저 읽으면
여러 개의 사탕을 사탕상자에 넣어두고 사탕을 꺼냅니다.
각각 사탕의 맛은 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)
시간복잡도
사탕의 종류는 맛으로 구분합니다.
맛은 1,000,000 가지 있습니다.
사탕은 2,000,000,000 개까지 존재하며
사탕을 꺼내거나 넣는 경우가 최대 100,000입니다.
즉, 최악일 경우 맛 100만 가지 중 원하는 사탕 하나하나 찾아 빼고 넣어야합니다.
크기가 100만인 배열을 뒤져서 순위를 찾아 사탕을 빼는 경우 최악은
1,000,000 * 100,000 = 1,000억 입니다.
즉, a가 1이라 할때 $O(MN)$의 시간 복잡도를 가지고 있다고 할 수 있습니다.
때문에 하나하나 순회하며 찾는 방법 말고 다른 알고리즘을 사용해야 합니다.
저희는 100만가지의 사탕을 검색할 때 시간 복잡도 O(M)이 아닌 $O(logM)$으로 만들면 해결할 수 있습니다.
문제 해결법
먼저 예제 입력을 따라가면 다음과 같은 순서로 작업이 진행됩니다.
1번 맛 사탕이 두 개 - > 2위
3번 맛 사탕이 3개 → 2위 + 3위 = 5위
까지 해당이 됩니다.
사탕의 맛을 인덱스라고 생각하면
candy[1] = 2
candy[3] = 3
임을 알 수 있습니다.
또한 순위를 알기 위해서는 두 사탕의 개수를 알아야 합니다.
어떠한 곳에 몇개의 사탕이 있는지 알기 위해서는
1위-2위 구간에 대한 합을 알아야하고
사탕의 개수 변동에도 적합해야 합니다.
때문에 저는 인덱스 트리를 사용하기로 했습니다.
인덱스 트리를 사용한 사탕을 나타내면 다음과 같습니다.
리프 트리의 인덱스는 사탕의 맛을 나타냅니다.
리프 트리의 가장 왼쪽 노드는 1번 맛 사탕을
리프 트리의 가장 오른쪽 노드는 1,000,000번 맛 사탕을 나타냅니다.
사탕상자 코드 구현
인덱스 트리를 1차원 배열로 나타내기 위해 S의 값을 구하고 tree 배열을 초기화 해줬습니다.
이후 query는 루트노트에서 시작하여 왼쪽 자식 노드와 현재 알아야하는 사탕 개수와 비교하고 왼쪽 자식에 있는 사탕의 개수가 적을 시 나머지 사탕을 오른쪽 자식 노드에서 가져오는 방식입니다.
리프 트리에 있는 1번 사탕이 있는 노드의 인덱스는 S입니다.
원하는 사탕 번호를 구할 때는 구한 노드의 인덱스 - S + 1해야 함에 주의해야 합니다.
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, S;
static int MAX_CANDY_FLAVOR = 1000000;
static int[] tree;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
S = 1;
while (S < MAX_CANDY_FLAVOR) {
S *= 2;
}
tree = new int[S * 2];
N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if (a == 1) {
int flavor = query(1, b) - S + 1;
update(S + flavor - 1, -1);
System.out.println(flavor);
} else if (a == 2) {
int c = Integer.parseInt(st.nextToken());
update(S + b - 1, c);
}
}
}
static int query(int node, int currRank) {
int answerNode = node;
if (currRank == 0) return answerNode;
if (node >= S) return answerNode;
int leftChild = node * 2;
int rightChild = node * 2 + 1;
if (tree[leftChild] >= currRank) {
answerNode = query(leftChild, currRank);
} else {
answerNode = query(rightChild, currRank - tree[leftChild]);
}
return answerNode;
}
static void update(int node, int count) {
if (node == 0) return;
tree[node] += count;
update(node / 2, count);
}
}
댓글