[프로그래머스, 12985] 예상 대진표 50/100

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

내 풀이

class Solution
{
    public int solution(int n, int a, int b)
    {
        //참가자가 2명이면 1라운드, 4명이면 2라운드, 8명이면 3라운드, 16명이면 4라운드, ...
        //총 라운드 수 => n = 2^x일때 x = log2 n
        
        //2번--1번 -> 1라운드 / 2번--4번 -> 2라운드 / 2번--6번 -> 3라운드
        //4번--6번 -> 3라운드 / 4번--8번 -> 3라운드 / 6번--8번 -> 2라운드
        //1번--15번 -> 4라운드 / 1번 -- 17번 -> 5라운드 / 1번 -- 31번 -> 5라운드
        //a와 b중 작은수가 1, 큰수가 2가 될때까지 라운드진행 후 라운드 수를 구하면 됨
        //홀수(N-1)이면 1을더해서 N으로 만든 후 진행
        //a가 17, b가 9라면 x를 9+1=10, y를 17+1=18로 만들고
        //10/2 = 5, 18/2 = 9 => 6, 10 1라
        //6/2 = 3, 10/2 = 5 => 4, 6 2라
        //4/2 = 2, 6/2 = 3 =>2, 4 3라
        //2/2 =1, 4/2 = 2 => 1, 2 4라
        
        //큰 수 구분
        int x, y = 0, roundNum = 1;
        if(a < b) {
            x = a;
            y = b;
        } else {
            x = b;
            y = a;
        }
        
        //x = 1, y = 2가 될때까지 roundNum을 증가시키면서 반복
        while(true) {
            //홀수 판단후, 홀수면 + 1
            if(x % 2 == 1) x += 1;
            if(y % 2 == 1) y += 1;

            //2로 나누고, 라운드수 + 1
            x /= 2;
            y /= 2;
            roundNum++;

            //결과 판단
            if(x == 1 && y == 2) break;
        }

        return roundNum;
    }
}

채점 결과

피드백 (100/100)

class Solution
{
    public int solution(int n, int a, int b)
    {
        //큰 수 구분
        int x = Math.min(a, b);
        int y = Math.max(a, b);
        int roundNum = 1;
        
        //x = 1, y = 2가 될때까지 roundNum을 증가시키면서 반복
        while(true) {
            //결과 판단
            if(x % 2 == 1 && y - x == 1) break;
            
            //홀수 판단후, 홀수면 + 1
            if(x % 2 == 1) x += 1;
            if(y % 2 == 1) y += 1;

            //2로 나누고, 라운드수 + 1
            x /= 2;
            y /= 2;
            roundNum++;
        }

        return roundNum;
    }
}

1. 큰 수 구분을 Math 클래스 사용

2. 결과 판단 if문을 위로 올림

3. 결과 판단 조건문을 x가 홀수고 y -x 가 1일때 탈출하게 변경

 

다른 풀이 : 비트연산을 활용한 풀이 https://programmers.co.kr/questions/20109

참가자 번호를 0부터 시작하게 1씩 뺀다음 xor 연산함
그 결과를 1씩 오른쪽으로 쉬프트하여 0이 될 때까지 ++

대진표의 제일 위 노드부터 0 1을 넣는다고 생각하면 이해 가능
(문제가 애초에 tree처럼 생겼기 때문에 bitwise operation으로 풀 수 있을 확률이 높음)

using namespace std;

int solution(int n, int a, int b) {
    int xor_result = (a - 1) ^ (b - 1);
    while (true) {
        static int ans = 0;
        if (xor_result) {
            ans++;
            xor_result >>= 1;
        } else {
            return ans;
        }
    }
}

 

Java로 바꾸면 아래와 같습니다.

class Solution
{
    public int solution(int n, int a, int b)
    {
        int xor_result = (a - 1) ^ (b - 1);
        
        int answer = 0;
        while (true) {
            if(xor_result != 0) {
                answer++;
                xor_result >>= 1;
            } else {
                return answer;
            }
        }
    }
}

 

1줄 짜리 풀이도 있어서 올려봅니다. 기본적인 원리는 같습니다

참조 : https://kimk2062.tistory.com/18

class Solution
{
    public int solution(int n, int a, int b)
    {
        return Integer.toBinaryString((a-1)^(b-1)).length();
    }
}

 

XOR 연산의 결과의 길이가 정답인것은 이해를 했는데,

 

왜 두 수에서 1을 빼줘야 정답이 나오는 지는 모르겠네요...