[백준 23792] K번째 음식 찾기 2 [Java]

문제

http://boj.ma/23792

요약

• 3개 그룹에서 K 번째로 맛있은 음식의 종류와 번호를 구하자.
• N, Q ≤ 1e5

---

풀이 과정

아이디어

3개의 그룹을 합쳐 정렬 후 K번째 음식을 찾는다면, $O(3NQ) = 3e10$으로 시간초과가 발생한다.

따라서 그룹을 합치치 않고, K번째 음식이 아닌, 어떤 음식 x에 대해 전체에서 x보다 작은 음식이 몇 개 인지 구 하는 문제로 재해석할 수 있다.

현재 그룹에 K번째 음식이 존재할 것으로 기대하며, 다른 그룹에는 K번째 음식보다 음식 맛이 작은 음식이 K - 1개 존재하는지 확인하면 된다.

현재 그룹의 임의의 음식(A[mid])에 대해 다른 그룹 내 음식(lowerBound(B, y, A[mid]) + lowerBound(C, z, A[mid]))과 현재 그룹의 음식 순서(mid + 1)이 k라면, A[mid]는 전체 그룹에서 k번째 음식임이 자명하다.

int l = 0, r = x - 1;
while (l <= r) {
    int mid = (l + r) >> 1;

    int rank = (mid + 1) + lowerBound(B, y, A[mid]) + lowerBound(C, z, A[mid]);
    if (rank == k) {
        sb.append(no).append(" ").append(mid + 1).append("\\n");
        return true;
    }

만약 k보다 작거나 크다면 현재 그룹에서 다른 음식을 적절히 선택하고 다시 위 과정을 반복하면 된다.

    if (rank < k) {
        l = mid + 1;
    } else {
        r = mid - 1;
    }
}
return false;

만약 현재 그룹에 k번째 음식이 존재하지 않는다면, 정답은 항상 존재하므로 다른 그룹에서 나올 때 까지 반복하면 된다.

if (solve(A, B, C, x, y, z, 1, k, sb)) continue;
if (solve(B, A, C, y, x, z, 2, k, sb)) continue;
solve(C, A, B, z, x, y, 3, k, sb);

성능 분석

• 시간 복잡도: O($log^2N$)
• 제출결과: Accepted / 1,372ms / 103,672KB

---

회고

이분 탐색을 처음 배울 때는 단순히 정렬된 배열에서 값을 찾는 용도로만 이해하고 있었다.

하지만 이번 문제를 통해 이분 탐색은 값을 찾는 용도가 아니라, 조건을 만족하는 지점을 찾는 용도임을 알 수 있었다. 이 문제는 k번째 음식을 직접 찾는 것이 아니라, 어떤 음식 x에 대해 전체에서 x보다 작은 음식이 몇 개인가라는 순위 함수 f(x) 를 정의하고 f(x) = k를 만족하는 x를 찾는 파라메트릭 서치 문제였다.

특히 인상 깊었던 점은, 한 그룹에서는 이분 탐색으로 후보를 좁히고, 다른 그룹에서는 lower_bound로 작은 값의 개수를 세는 방식으로 이분 탐색이 중첩되어 O(log² N) 구조가 된다는 점이었다.

앞으로 조건을 만족하는 또는 특정 순서를 요구하는 문제에 대해, 정렬보다는 순위 함수로 재해석이 가능할지 고민해볼 것 같다.

---

참고

문제

http://boj.ma/23792

23792번: K번째 음식 찾기 2

소스코드

http://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/23792.java

problem-solving/baekjoon-online-judge/normal/23792.java at main · rogi-rogi/problem-solving