[자바] 백준 7469 - K번째 수 (java)

 문제 : boj7469

---

 

필요 알고리즘 개념

• 정해 : 머지 소트 트리 + 세그먼트 트리
  
  • 정해는 세그먼트 트리를 응용한 머지 소트 트리로 보인다.
• 내 경우 : 펜윅 트리
  
  • 머지 소트 트리를 펜윅 트리로 적용시켜서도 풀 수 있다.
• 매개 변수 탐색 (parametric search)
  • 이분 탐색의 응용 방법인 매개 변수 탐색이 필요한 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  일반적으로는 대부분 세그먼트 트리에 각 노드를 배열로 처리한 머지 소트 트리를 사용해 풀었다. 내 경우엔 아직 세그먼트 트리를 정식으로 공부하지 않았으므로, 내가 알고 있는 선에서 처리해보려고 펜윅 트리로 응용해서 적용해봤다. 따라서 정해가 아니고, 내 방식대로 푼 것이므로 머지 소트 트리로 풀려면 다른 풀이를 보기 바란다.

 

  수열과 쿼리 3에서 좀 더 +@ 된 문제이다. 일단 수열과 쿼리 3을 먼저 풀고 이 문제를 푸는걸 추천한다. 해당 구간에서 k번째 수라는 의미는 즉, 해당 구간에서 어떠한 수 x보다 큰 수가 '구간내의 수의 개수 - k'개거나, x보다 작은 수가 k-1개 라는 것과 같은 말이다. 이게 가능한 것은 입력이 모두 다른 수 이기 때문이다. 그렇지 않은 경우라면 이 방식으로 풀 수 없다.

 

  머지 소트 트리는 세그먼트 트리의 각 노드를 정렬된 배열로 처리한다. 마찬가지로, 펜윅 트리의 각 노드를 정렬된 배열로 처리하더라도 이 문제는 문제없이 풀 수 있다. 다만 펜윅 트리는 [1, x] 구간의 k보다 큰 원소의 개수를 알 수 있는게 문제인데, [a, b] 구간의 k보다 큰 원소의 개수는 결국 [1, b] 구간의 k보다 큰 원소의 수에서 [1, a-1] 구간의 k보다 큰 원소의 수를 빼는 것으로 구할 수 있다.

 

  우선 어떠한 구간에서 어떠한 수 x보다 큰 값의 개수를 구하는 방식은, 수열과 쿼리 3를 이 문제를 푼 것 처럼 펜윅트리를 응용해 풀어둔 내 글을 참고하자. k번째 수를 구하기 위해서는 정확히 x보다 큰 수가  '구간내의 수의 개수 - k'가 되는 지점을 찾으면 된다. 애초에 정렬이 되어있는 펜윅트리이므로 이건 이분탐색을 응용한 매개변수 탐색을 사용해 구할 수 있다. 코드의 getAnswer()를 참고해보자.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    ArrayList<Integer>[] bit;
    int n, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;

    private void update(int idx, int val) {
        while (idx <= n) {
            bit[idx].add(val);
            idx += idx&-idx;
        }
    }

    private int getCntOfOver(ArrayList<Integer> list, int k) {
        int res = Collections.binarySearch(list, k+1);
        if (res < 0) {
            res += 1;
            res = -res;
        }
        return list.size() - res;
    }

    private int prefixSumOfCnt(int idx, int k) {
        int cnt = 0;
        while (idx > 0) {
            cnt += getCntOfOver(bit[idx], k);
            idx -= idx&-idx;
        }
        return cnt;
    }

    private int query(int i, int j, int k) {
        return prefixSumOfCnt(j, k) - prefixSumOfCnt(i-1, k);
    }

    private int getAnswer(int a, int b, int c) {
        c = b-a+1-c;
        int start = min;
        int end = max;
        while (start<=end) {
            int mid = (start+end)/2;
            if (query(a,b,mid) > c)
                start = mid+1;
            else
                end = mid-1;
        }
        return start;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        bit = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) bit[i] = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            int cur = Integer.parseInt(st.nextToken());
            if (max<cur) max = cur;
            if (min>cur) min = cur;
            update(i, cur);
        }
        for (int i = 1; i <= n; i++) Collections.sort(bit[i]);

        StringBuilder sb = new StringBuilder();
        while (m-->0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            sb.append(getAnswer(a,b,c)).append('\n');
        }
        System.out.print(sb);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}