Lv.2 : 예상 대진표

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 토너먼트에서 n명의 사람 중 a번째 사람과 b번째 사람이 맞붙게 될 라운드를 리턴한다.
  • a와 b는 서로 만나기 전 까지 항상 승리한다.
  • 승자들을 다시 1부터 n`까지 번호를 매겨 붙게된다.

🔸 문제 풀이 🔸

• a < b일때, b-a == 1 이고, a가 홀수, b가 짝수일때 맞붙게된다.
• 위 조건이 만족 할 때까지 a와 b 게임을 진행시킨다.

---

🔸 코드 🔸

class Solution
{
    public int solution(int n, int a, int b)
    {
        if(a > b) {
            int temp = a;
            a = b;
            b = temp;
        }
        
        int answer = 1;
        
        while(!(b-a == 1 && a%2 == 1 && b%2 == 0)) {
            answer++;
            a = a/2 + a%2;
            b = b/2 + b%2;
        }
        return answer;
    }
}

🔸 코드 해석 🔸

• a < b 가 되도록 맞춰준다.
• 게임이 진행 될 때 2로 나는 몫 + 2로 나눈 나머지로 바꾸면 다음 라운드 번호를 계산할 수 있다.

---

🔸 end 🔸

• 원리 이해가 쉬워서 손쉽게 풀이할 수 있었다.
• 하지만 다른 풀이를 보니 문제의 숨은 원리 파악이 부족했다고 생각했다.
  • 1번 풀이 
    • 나머지는 생각하지 않고, a와 b에서 -1 후 각각 2로나눈 몫이 같아 질 때까지 2로 나눈다.
    • 2로 나눠서 몫이 같으면 맞붙는 상황이라는게 생각하지 못한 부분이다.
  • 2번 풀이
    • 획기적인 풀이라고 생각하는데, 한 줄로 계산할 수 있다.
    • 2로 계속 나눠서 몫이 같아지는 라운드를 계산하는 방법은, 2진수에서 겹치지 않는 1 중 가장 큰 값까지의 길이라는 원리라고 이해했다. 2진법을 잘 이용하니 기가막힌 것 같다.

Integer.toBinaryString((a-1)^(b-1)).length();