2243번: 사탕상자
첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다.
www.acmicpc.net
세그먼트 트리 + 이진탐색으로 해결하였다.
처음에는 이진탐색으로만 문제를 풀었는데 시간초과가 났다.
세그먼트 트리에서 노드의 범위는 1부터 1000000까지이다. 사탕의 번호가 1부터 1000000까지 존재하기 때문이다. 각 노드에는 해당 사탕의 개수가 들어있다.
A = 2인 경우, 사탕상자의 사탕에 변화가 생기므로 세그먼트 트리의 update() 메서드를 실행한다.
A = 1인 경우, 수정이가 요구한 순위의 사탕이 어떤 맛의 사탕인지를 알기 위해서 이진탐색을 진행해야한다. 범위를 반으로 좁혀가면서 중간값을 구하고, 1부터 중간값(mid)까지의 사탕의 개수의 합(sum)을 세그먼트 트리의 sum() 메서드를 통해 구한다.
만약 구한 합(sum)이 수정이가 요구한 순위(B)보다 크거나 같다면, 범위를 중간값보다 왼쪽인 범위로 좁히고, 수정이가 요구한 순위(B)보다 작다면, 범위를 중간값보다 오른쪽 범위로 좁힌다.
여기서 세그먼트 트리를 이용하여 합을 구하기 때문에 시간복잡도가 O(logN)이 된다.
세그먼트 트리를 이용하지 않고 1부터 중간값(mid)까지의 사탕 개수의 합을 단순히 for문을 이용하여 구하면 시간복잡도가 O(N)이 걸린다. 이 문제에서는 합을 구하는 과정에서 세그먼트 트리를 이용하지 않으면 시간 초과가 발생한다.
전체 코드 :
'BOJ' 카테고리의 다른 글
| [백준 3653번] 영화 수집 (java) (3) | 2021.04.21 |
|---|---|
| [백준 13904번] 과제 (java) (0) | 2021.04.20 |
| [백준 1495번] 기타리스트 (java) (0) | 2021.04.19 |
| [백준 1720번] 타일 코드 (java) (0) | 2021.04.16 |
| [백준 1958번] LCS 3 (java) (0) | 2021.04.13 |