[2017 팁스타운] 예상 대진표

[2017 팁스타운] 예상 대진표

🙋‍♂️ 들어가며

이번 문제는 틀렸던 접근법과 맞는 풀이 2개로 작성할 것이다.

우선 나는 a,b 중 작은 값 1개를 start, 큰값을 target으로 만들어 while문 내의 for문의 범위를 i = start, i <= power * 2 만큼 증가시켜서 i == target일때 횟수를 반환하면 된다고 생각했다 내 추측의 근거로는 다음 그림과 같다

ex) 12, 16이 대결할때 3번째에서 만난다.

❌ 틀린 코드

class Solution {
    public int solution(int n, int a, int b) {
        int cnt = 1;
        
        int power = 1;
        boolean stop = false;
        int start = Math.min(a,b);
        int target = Math.max(a,b);
        
        while (true) {
            for (int i = start; i <= start + power; i++) {
                if (i == target) {
                    stop = true;
                    break;
                }
            }
            if (stop) break;
            cnt++;
            power *= 2;
        }
        
        
        return cnt;
    }
}

testcase는 맞았으나 제출할때는 틀렸다.

다시 보니 반례가 있었다

a = 2

b = 3

일 경우에 cnt = 2 인데

나의 코드로는 1을 반환하기 때문이다

🙋‍♂️ 다른 접근

이번에는

a /= 2

b /= 2

를 수행하면 되겠다고 생각했으나 역시 a = 2, b = 3일때 틀린다.

아 그렇다면 다음과 같이 수행해보자

(a+1) /= 2

(b+1) /= 2

✅ 정답 코드

class Solution {
    public int solution(int n, int a, int b) {
        int cnt = 0;
        
        while (true) {
            a = (a+1) / 2;
            b = (b+1) / 2;
            cnt++;
            if (a == b) break;
        }
        
        return cnt;
    }
}

맞다.

느낀점

문제를 잘 읽자

문제에 N/2 라고 힌트를 주었는데 못 읽은 나의 잘못이다.