[프로그래머스] 예상 대진표

https://programmers.co.kr/learn/courses/30/lessons/12985

코딩테스트 연습 - 예상 대진표

 

프로그래머스 Lv2 문제이고, 시뮬레이션 문제이지만 이분탐색을 활용한 DP 로 해결이 가능하다.

 

기본적으로 데이터 양이 기하급수적으로 많은 경우에는 일반 탐색보다는 이분 탐색의 복잡도가 O(logN) 이기 때문에 왠만하면 시간 초과로 문제가 생기지는 않는다.

 

저는 해결 방법으로 이분 탐색을 수행하면서 각 단계별로 위치를 저장하는 배열을 활용해서 A 참가자와 B 참가자가 언제 만나는지를 계산하였습니다.

 

예제에서는 A : 4, B : 7 이 주어졌는데, 기본적으로 꼭대기를 기준으로 1~4, 5~8 로 나눌 수 있고, A와 B는 서로 반대편에 위치하기 때문에 수식으로 기본 라운드값 - {배열이 겹치는 카운트) 로 계산하여 응답값으로 출력하면 된다.

 

예제 코드는 아래와 같다.

 

class Solution
{
    public static int solution(int n, int a, int b) {

        int round = 0;
        int temp_n = n;
        while (temp_n > 1) {
            round++;
            temp_n >>= 1;
        }
        // 0 은 왼쪽, 1 은 오른쪽
        int[] dir_a = new int[round];
        int[] dir_b = new int[round];

        int[][] dir = new int[2][round];

        for (int i = 0; i < dir.length; i++) {
            int left = 1;
            int right = (1 << round);
            int target = i == 0 ? a : b;
            for (int j = 0; j < round; j++) {
                int mid = (left + right) / 2;
                if (target <= mid) {
                    right = mid;
                    dir[i][j] = 0;
                } else {
                    left = mid + 1;
                    dir[i][j] = 1;
                }
            }
        }

        int count = 0;
        for (int i = 0; i < round; i++) {
            if (dir[0][i] == dir[1][i]) count++;
            else break;
        }
        return round - count;
    }
}