[백준] 2243번 : 사탕상자 - 자바(JAVA)

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

2243번: 사탕상자

 

문제 해석

사탕의 맛이 좋고 나쁨이 1부터 1,000,000까지의 정수로 구분된다.

1이 가장 맛있는 사탕이며 1,000,000은 가장 맛없는 사탕입니다.

사탕상자의 손을 댄 횟수는 10만번

A,B 또는 A,B,C가 입력으로 주어진다.

A = 1 이라면 사탕을 꺼내는 경우이다.

A = 2 라면 사탕을 넣는 경우이다.

이때 B는 넣을 사탕의 맛을 나타내는 정수이고 C는 그러한 사탕의 개수이다.

C가 양수일때는 사탕을 넣는 경우이고 음수일 경우에는 빼는 경우입니다.

 

문제의 입출력 예시로 이해해 보겠습니다.

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

6번 사탕상자에 손을 댑니다.

첫번째로 사탕상자에 1번맛 사탕 2개를 넣습니다.

두번째로 사탕상자에 3번맛 사탕 3개를 넣습니다.

세번째로 사탕상자에서 2번순위의 사탕을 꺼냅니다.

 

(현재 사탕상자는 1 1 3 3 3 으로 구성되어 있기 때문에 2번순위인 1이 나오게 됩니다)

(이후의 사탕상자는 1 3 3 3 으로 구성됩니다)

 

네번째로 사탕상자에서 2번순위의 사탕을 꺼냅니다.

(현재 사탕상자는 1 3 3 3 으로 구성되어 있기 때문에 2번순위인 3이 나오게 됩니다)

(이후의 사탕상자는 1 3 3 으로 구성됩니다)

 

다섯번째로 사탕상자에 1번맛 사탕 1개를 뺍니다.

(이제 사탕상자는 3 3 3 으로 구성됩니다)

 

여섯번째로 사탕상자에 2번 순위의 사탕을 꺼냅니다.

2번순위인 3이 나오게 됩니다.

 

 

문제 풀이 전 설계

10만번의 행위에 대해서 사탕을 꺼내고 넣고 해야 합니다.

최대 O(NlogN)만에 해결해야 할 것 같습니다.

만약 사탕상자가 정렬되어 있다면 이분탐색을 통해서 NlogN으로 해결할 수 있을 것 같습니다.

하지만 그러기 위해서는 사탕상자에 사탕을 넣어주는 작업을 해야하는데 여기서 사탕의 총 개수가 20억개가 최대이므로 넣는 작업을 O(N)으로 수행한다면 안될 것 같습니다.

 

넣어주는 작업 코드 예시

for(int j=0; j<count; j++){
	candyBox.add(taste);
}
candyBox.add(taste);
//이분탐색을 위한 정렬
Collections.sort(candyBox);

 

이것을 반복을 줄이기위해서 (taste, count)를 가지는 객체로 관리해도 되지만 사탕의 개수가 백만개이기 때문에 결국에는 10만 * 100만은 안될 것 같습니다.

 

문제 풀이

순위 정보가 필요한데 이 값이 계속 바뀌게 됩니다.

세그먼트의 인덱스를 사탕의 맛으로 잡고 인덱스에 들어있는 값을 갯수로 가진 합 세그먼트 트리로 풀이하면 됩니다.

예를 들어 맛이 1개 사탕2개 2인 사탕 1개 3인 사탕 1개가 있다면 세그먼트 트리를 다음과 같이 생성하면 됩니다.

 

 

https://loosie.tistory.com/659

B번맛 사탕 출력하기 작업

현재 들어있는 사탕 중 B순위에 해당하는 것을 꺼내주는 로직으로 구간합을 이용해 이분탐색을 수행합니다.

작업은 다음과 같이 진행됩니다.

 

target = 3 예시

 

세그먼트 트리의 인덱스는 다음과 같습니다. ( root는 1부터 시작하며 왼쪽자식은 부모 *2 , 오른쪽 자식은 부모* 2 + 1)

tree[1] = 4

tree[2] = 3

tree[3] = 1

tree[4] = 2

tree[5] = 1

 

target <= tree[2]이므로 왼쪽 트리로 이동한다 index = 2

target > tree[4]이므로 오른쪽 트리로 이동한다 index = 5

5번 인덱스에 속하는 2번맛 사탕을 출력한다.

 

또한 캔디를 찾으면 수동으로 s번맛 사탕을 -1 감소시켜줘야 합니다.

 

코드

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

public class Main_2243_사탕상자 {

    static final int SIZE = 1_000_001;
    static int[] tree;
    static final int GET = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        tree = new int[SIZE*4];
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            int operation = Integer.parseInt(st.nextToken());
            int target = Integer.parseInt(st.nextToken());
            if(operation == GET) {
                int candy = query(1, SIZE, 1, target);
                sb.append(candy+"\n");
            }else {
                int count = Integer.parseInt(st.nextToken());
                update(1, SIZE, 1, target, count);
            }
        }
        System.out.println(sb.toString());
    }
    static int query(int start, int end, int idx, int target) {
        if(start == end) {
            update(1, SIZE, 1, start, -1);
            return start;
        }

        int mid = (start+end)/2;
        if(target <= tree[idx*2]) {
            return query(start, mid, idx*2, target);
        }else {
            return query(mid+1, end, idx*2+1, target-tree[idx*2]);
        }
    }

    static void update(int start, int end, int idx, int target, int dif) {
        if(target < start || end < target) return;

        tree[idx] += dif;
        if(start == end) return;

        int mid = (start+end)/2;
        update(start, mid, idx*2, target, dif);
        update(mid+1, end, idx*2+1, target, dif);
    }
}

 

 

 

출처

https://loosie.tistory.com/659

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