일단 시작해보는 블로그

[알고리즘_풀이] 프로그래머스 - 예상 대진표 java 본문

카테고리 없음

[알고리즘_풀이] 프로그래머스 - 예상 대진표 java

Selina Park 2020. 3. 4. 23:19

문제

https://programmers.co.kr/learn/courses/30/lessons/12985?language=java

 

코딩테스트 연습 - 예상 대진표 | 프로그래머스

△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라

programmers.co.kr

생각

홀수인 사람은 항상 자신+1인 짝수와 대결을 하고 

짝수인 사람은 항상 자신-1인 홀수와 대결을 한다.

 

또, 이긴다면 다음 라운드는 (속해 있는 팀의 짝수인 사람/2)번째로 참가하게 될 것이다.

 

따라서 무조건 짝수로 만들어 준 다음에 2로 나누고 둘이 겹치지 않을 때까지 반복(재귀 or loop)한다.

 

풀이

재귀

class Solution
{
    static int answer = 0;
    public static void recursion(int n, int a, int b) {
        if(a == b) return;

        if(a%2 == 1) {
            a += 1;
        }
        if(b%2 == 1) {
            b += 1;
        }
        
        answer += 1;
        recursion(n, a/2, b/2);
    }

    public int solution(int n, int a, int b){

        recursion(n, a, b);

        return answer;
    }
}

 

loop (반복문)

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

        return answer;
    }
}
Comments