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

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

 

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

프로그래머스

---

접근

토너먼트가 진행될 때마다 변하게 되는 순서에 포커스를 두어야 하는 문제입니다.

첫번째 케이스를 예시로 들면, 1~8번까지의 참가자는 다음과 같이 순서를 부여받게 됩니다.

4번 참가자와 7번 참가자가 몇 번째에 만나는지 알기 위해서는 각각의 숫자를 반복문을 돌리면서 새로 부여될 번호로 바꾸고, 두 숫자가 같아질 때까지 몇 번이나 순회를 하였는지를 구하면 되겠습니다.

 

어려웠던 부분은 새로 부여 받을 순서를 구하는 공식이었습니다.

결론적으로 해당 숫자가 a라면 a / 2 + a % 2 (2에 대한 나머지와 몫을 더함) 으로 재할당 하는 방식으로 구할 수 있었으나 도출해내기가 쉽지 않았습니다.

 

a / 2는 이진 트리에서 한 레벨 위로 이동하는 것으로, a % 2는 원래 위치가 홀수 번째 노드일 경우에 처리하는 방법으로 이해하면 되겠습니다.

 

... 글 쓰면서 생각해보니 더 간단한 방법이 있었습니다. 그냥 해당 숫자에 1을 더하고 2를 나누는 방식을 적용하는 게 낫겠습니다.

3, 4의 경우 1을 더하면 4, 5가 되기 때문에 몫을 구하면 2로 통일됩니다.

 

코드

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

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