[Programmers] 예상 대진표

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

프로그래머스

문제 설명

토너먼트 대진표가 주어질 때 a와 b가 만나는 라운드를 구해야 한다. 2의 n승만큼 인원이 주어지므로 부전승은 없다. 처음 문제를 보고 이진 트리 구조가 생각나서 트리를 활용해 부모 노드가 같은 경우를 찾으려고 했으나 너무 과한 것 같다고 생각했다. 그래서 n을 2로 나누어 줄여나가는 방식으로 해결했다. 처음엔 재귀로 했더니 런타임 오류(아마 스택오버플로우로 추정된다)가 절반 가까이 발생했다. 그래서 while 문으로 제출했더니 오류나던 케이스들이 그대로 시간 초과가 발생했다. 문제를 생각해보니 n은 2의 지수승이고 최대 20승인데 n에 대하여 연산을 수행하는 코드를 작성하여 시간 초과가 발생한 것으로 판단했다. 그래서 n 대신 a와 b에 대한 연산을 하도록 수정하여 문제를 해결했다.

코드

class Solution
{    
    public int solution(int n, int a, int b)
    {
        int depth = (int) (Math.log(n) / Math.log(2));
        int small = Math.min(a, b);
        int large = Math.max(a, b);
        
        while (true) {
            n /= 2;
            if (small <= n && n < large) break;
            if (small > n) small -= n;
            if (large > n) large -= n;
            depth--;
        }
        
        return depth;
    }
}