[백준 / BOJ] 2812 크게 만들기 (Java / 세그먼트 트리)

문제

출처 : https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

N자리의 수가 주어지며 이 수에서 K개의 숫자를 제거했을때 얻는 가장 큰 수를 구하는 문제이다.

---

풀이

세그먼트 트리로 푼 문제다.

문제를 N자리의 수에서 (N-K)개의 숫자를 선택하는 문제로 바꾼다면, 현재 선택가능한 범위 (left ~ right)에서 (N-K)번 숫자를 뽑아 최댓값을 만드는 문제로 바뀌게 된다. 

이때, left ~ right의 범위는 최대 250,000만큼 차이가 날 수 있으므로, 완전탐색으로 현재 범위에서 최댓값을 찾는다면, (250,000 * (250,000-1)) 만큼 반복하게되어 TLE를 받는다. 따라서, 현재범위에서 최댓값을 빠르게 찾아줘야했는데, N개의 수를 정렬할 수 없으므로 이분탐색을 사용할 수 없어 세그먼트 트리를 이용해 구현했다.

(N개의 수를 정렬할 수 없는 이유는 N-K개의 숫자를 뽑았을때 자릿수의 상대관계가 유지되어야 하기 때문이다.)

 

세그먼트 트리로 구현할 경우 시간복잡도는 다음과 같다.

1. 세그먼트 트리 구조를 만드는데, O(NlogN)

- 이 문제의 경우 세그먼트 트리를 만드는데 필요한 시간복잡도가 최악의 경우에도 O((N^2)logN)가 아닌 O(NlogN)인데, 항상 자신의 idx를 포함하는 범위만 업데이트 해주기 때문에 N*1*logN이 된다. 따라서, lazy propagation을 사용하지 않아도 TLE가 나지 않는다.

2. N-K개의 수를 뽑아 최댓값을 만드는 과정에 O((N-K)logN)

 

알고리즘은 다음과 같다.

1. left ~ right범위의 최댓값을 세그먼트 트리에 저장한다. 단, 값이 같다면 다음 선택에서 선택범위를 더 넓혀주기 위해서 idx가 앞에오는 수를 저장한다. 

 

2. N자리의 수에서 (N-K)개의 숫자를 뽑는다.

 

주요 소스코드

    private void selectNum(int left, int right, int select){
        NumIdx numIdx = querySeg(0, N-1, 1, left, right);
        this.resultPrinter.append(numIdx.num);
        int remainNums = N - (numIdx.idx+1);
        int nextLeft = numIdx.idx + 1;
        int nextSelected = select - 1;
        int nextRight = nextLeft + (remainNums-nextSelected);
        if(nextSelected == 0) return;
        this.selectNum(nextLeft, nextRight, nextSelected);
    }

세그먼트 트리 코드는 기본적인 세그먼트 트리 구현과 비슷해 크게 어렵지 않으니 전체 소스코드에서 보도록 하자

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/2812%20크게%20만들기/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃