[Coding Test] 프로그래머스 2단계 - 예상 대진표

📚 문제

 

✏️ 메모 1

무조건 왼쪽 홀수, 오른쪽 짝수.
1 - 2 가 붙으면 둘 중 누가 이기던 간에 이긴 참가자가 1번이 됨.
3 - 4 가 붙으면 둘 중 누가 이기던 간에 이긴 참가자가 2번이 됨.
5 - 6 이 붙으면 ~ 3번이 됨.
7 - 8 이 붙으면 ~ 4번이 됨.
3 참가자 > (3 + 1) / 2  = 2
7 참가자 > (7 + 1) / 2 = 4 
a 와 b 가 차이가 1이 될 때까지 반복. 

import java.lang.Math;

class Solution
{
    public int solution(int n, int a, int b) {
        int answer = 1;

        while ( Math.abs(a - b) != 1 ) {
            if (a % 2 == 0 ) {
                // 짝수이면 
                a = a / 2;
            } else {
                // 홀수이면
                a = (a + 1) / 2;
            }
            
            if (b % 2 == 0 ) {
                // 짝수이면 
                b = b / 2;
            } else {
                // 홀수이면
                b = (b + 1) / 2;
            }
            
            answer ++ ;
        }

        return answer;
    }
}

 

테스트 7, 9, 27, 33  실패. 왜?

✏️ 메모 2

둘이 맞붙는 순간, 무조건 둘 중 작은 수가 홀수 큰 수가 짝수여야 함. 

아니면 다른 경기를 또 해서 와야 함. 

!!! 

 

- 반례 - 

int n = 8; // 참가자 수
int a = 4; // 참가자 A
int b = 5; // 참가자 B

<라운드 1> 
a = 4 / 2 = 2;
b = (5 + 1) / 2 = 3;

이때
Math.abs(a - b) = 1 의 조건을 만족해버림.

 

🔎 문제해결

import java.lang.Math;

class Solution
{
    public int solution(int n, int a, int b) {
        int answer = 1;
        
        // a 와 b의 차이가 1이, 둘 중 최솟값이 홀수여야 반복문 끝남. 
        while ( !(Math.abs(a - b) == 1 && Math.min(a, b) % 2 == 1)) {
            if (a % 2 == 0 ) {
                // 짝수이면 
                a = a / 2;
            } else {
                // 홀수이면
                a = (a + 1) / 2;
            }
            
            if (b % 2 == 0 ) {
                // 짝수이면 
                b = b / 2;
            } else {
                // 홀수이면
                b = (b + 1) / 2;
            }
            
            answer ++ ;
        }

        return answer;
    }
}

// 무조건 왼쪽 홀수, 오른쪽 짝수.
// 1 - 2 가 붙으면 둘 중 누가 이기던 간에 이긴 참가자가 1번이 됨.
// 3 - 4 가 붙으면 둘 중 누가 이기던 간에 이긴 참가자가 2번이 됨.
// 5 - 6 이 붙으면 ~ 3번이 됨.
// 7 - 8 이 붙으면 ~ 4번이 됨.
// 3 참가자 > (3 + 1) / 2  = 2
// 7 참가자 > (7 + 1) / 2 = 4 
// a 와 b 가 차이가 1이 될 때까지 + 왼쪽 홀수, 오른쪽 짝수. 조건 될 때까지 반복.