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

문제

N명이 참가하는 토너먼트에서 A번 참가자와 B번 참가자가 몇 번째 라운드에서 만나게 되는지를 구하는 문제입니다.

라운드는 다음과 같이 진행됩니다:

• 1라운드에서는 1번 vs 2번, 3번 vs 4번, …
• 이긴 사람은 다음 라운드에 진출하며, (번호 + 1) / 2의 번호를 받게 됩니다.

🛠 사용 기술

• Java 기본 문법 (while, Math.abs, 산술 연산자)
• 시뮬레이션 알고리즘
• 비트 연산 없이 자연수 순서 기반의 라운드 추적

---

Approach 1 ⭕

💻 코드

class Solution
{
    public int solution(int n, int a, int b)
    {   
        int round = 1;
        while((a+1)/2 != (b+1)/2){
            a = (a/2 + a%2);
            b = (b/2 + b%2);
            round++;
        }
        
        return round;
    }
}

🔍 접근법

• 문제의 핵심은 A번과 B번 참가자가 같은 조에 배정되는 라운드를 찾는 것입니다.
• 각 참가자는 다음 라운드에 (x + 1) / 2로 올라가기 때문에, 이 과정을 반복하며 두 번호가 같아질 때까지 시뮬레이션합니다.
• 두 번호가 같아지는 순간이 두 사람이 직접 맞붙는 시점입니다.

---

느낀 점 및 메모 💡

• (x + 1) / 2라는 수식을 통해 자연스럽게 다음 라운드 번호로 이동할 수 있음을 알게 되었고, 지속적인 번호 갱신을 통해 결국 두 참가자의 대진 시점을 정확히 계산할 수 있었다.
• 처음에는 Math.abs(a - b) == 1인 경우 두 참가자가 붙는다고 착각했지만, 실제로는 짝수-홀수 순서에 따라 같은 조에 있을 수도, 아닐 수도 있음을 알게 되었다. 예를 들어 4, 5번이라면 abs 값은 1이지만, 해당 라운드에서 서로 맞붙지 않는다.
• 처음엔 두 값의 차를 절댓값으로 비교했지만, 실제론 단순하게 x != y 비교만으로 충분했다. 불필요한 연산을 줄이는 것도 코드 최적화의 중요한 습관 중 하나다.