프로그래머스_예상 대진표_day16

알고리즘 챌린지 16일 차이다. 지난주에 야근과 퇴근 후 바쁜 일정으로 인하여 1주를 통으로 쭉 밀려버렸다...
밀린 수준이 아니라 챌린지의 존재 자체를 까먹어 버렸다... 3월 새 학기를 시작하는 대학생의 마음으로 다시금 시작해 보자.

오늘은 프로그래머스 level2 중에서 쉬운 문제를 가져왔다. 

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

프로그래머스

문제를 읽다 보면 난해해 보이지만 조건자체가 규칙이 있어 간단한 문제이다. 
조건부터 차근차근 분석해 보자. 

먼저, 모든 참가자의 수는 2의 지수 승으로 주어진다고 했다. 간단하게 작은 수( 2^2 = 4 )만 예시를 들어봐도 부전승 없이 결승전에서 최종 승자가 나올 수밖에 없음을 알 수 있다.
또한, 최대 범위가 2^20이고, 한 라운드가 진행되면 참가자의 반토막씩 사라지기 때문에, 반복 횟수는 주어진 수의 2의 지수로 삼으면 될 것 같다.  시간 복잡도는 고려할 필요가 없어 보인다. 예를 들어 2^n의 참가자가 나왔다고 하면, 승자를 가리기 위해 진행해야 하는 라운드는 최대 n라운드이다. 즉 반복의 최대도 n회인 것이다. 

자, 그렇다면 각 반복에서 우리가 체크해야 할 부분은 무엇일까? 현재 라운드에서 주어진 수 A, B가 대전을 하는지를 확인해야 한다. 하지만 이전 라운드에서 승자는 새로운 번호를 부여받는다. 우리는 2명의 참가자만 추적하면 되는데, 두 참가자는 승리가 보장되어 있다. 반복 횟수도 적기 때문에  1라운드부터 bottom-up 방식으로 하나씩 추적해도 충분히 가능하다는 뜻이다. 

간단한 규칙이 있다. 특정 수 A가 짝수라면, A가 다음 라운드에서 부여받을 번호는 2로 나눈 몫이다. 
특정 수 B가 홀수라면, B가 다음 라운드에서 부여받을 번호는 2로 나눈 몫 + 1이다.
작은 수가 홀수 이면서, 두 값의 차이가 1인 경우 A와 B가 대전을 한다고 판단할 수 있다. 
그림으로 설명을 해볼까 했는데, 코드로만 봐도 쉽게 이해가 가능할 것 같다. 

Java

class Solution
{
    public int solution(int n, int a, int b)
    {
        int round = 1;

        int jisu = (int) (Math.log10(n) / Math.log10(2));
        
        int max, min; 
        max = a > b ? a : b;
        min = a > b ? b : a;
        
        while(true) {
            if(min%2==1 && max-min == 1) break;
            
            if(max%2 == 0) max = max/2;
            else max = max / 2 + 1;
            
            if(min%2 == 0) min = min/2;
            else min = min / 2 + 1;
            
            round++;
            
        }

        return round;
    }
}