[PGM_12985] 예상 대진표 (java)

문제링크

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

코딩테스트 연습 - 예상 대진표

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 수학

1. 문제 이해

토너먼트로 경기를 진행하게 된다. 이 때 토너먼트 게임은 1 vs 2, 3 vs 4, 5 vs 6 ... 로 진행되며 1 vs 2의 승자와 3 vs 4의 승자가 다음 토너먼트에서 경기를 진행하는 방식이다.

 

토너먼트를 진행하는 사람의 수 n과 두 명의 선수의 번호 a, b가 주어졌을 때 두 선수가 토너먼트 경기의 몇번째 경기에서 만날 수 있을지를 찾는 문제이다. (몇번째 경기란, 해당 선수가 몇번의 승리만에 상대를 만날 수 있는지를 의미한다.)

 

여기서 n으로 입력되는 값이 2의 n승이 온다는 조건때문에 토너먼트에서 부전승이 없게 된다.

 

2. 접근방법

토너먼트 경기를 정확히 절반씩 나누어 문제를 접근하였다. 결승전은 절반으로 나누어 생각해보면 왼쪽 토너먼트의 최종 우승자와 오른쪽 토너먼트의 최종 우승자의 경기라고 할 수 있다. 그리고 그 둘은 완전히 대칭의 모양을 보여줄 것이다. 그리고 왼쪽의 우승자는 절대로 오른쪽의 토너먼트의 사람들과 결승전이 되기 전까지는 겨루어볼 수 없다.

 

이러한 토너먼트의 결승전의 특징을 토너먼트의 모든 경기들로 일반화하여 생각해보겠다.

1. 토너먼트는 반으로 갈랐을 때 서로 대칭이다.

2. 어느 경기를 기준으로 왼쪽에서의 우승자와 오른쪽에서의 우승자가 겨루게 된다.

3. 왼쪽의 우승자는 오른쪽의 우승자와 겨루어 볼 수 없다.

 

3. 세부 해결방안

//둘 다 같은 위치에 포함 될 때
if(inPlayer(startNumber,finishNumber,playerA) && inPlayer(startNumber,finishNumber,playerB)) {
    int partition = startNumber + (finishNumber - startNumber + 1)/2;
    int left = recursiveSolve(startNumber,  partition-1 , playerA, playerB);
    int right = recursiveSolve(partition,finishNumber,playerA,playerB);
    return left == -1 ? right : left;
}

- 만약 두명이 같은 위치에 있다면 그 부분을 다시 반으로 갈라서 반복 확인한다.

//둘 다 포함되어있지 않을 때
else if(!inPlayer(startNumber,finishNumber,playerA) && !inPlayer(startNumber,finishNumber,playerB))
    return -1;

- 둘 다 없다면 그 부분은 더 이상 확인할 필요가 없으니 더 이상 확인하지 않는다.

//다른 토너먼트로 포함되어있을 때
int count = (finishNumber - startNumber + 1);
int result = 0;

//토너먼트 진행 횟수 계산
while (count != 0){
    count /=2;
    result++;
}
return result;

- 둘 중 하나만 있다면 그 지점까지 올라갈 때 치루어지는 경기의 수를 계산해준다.

구현코드

package pgm_12985;

public class Solution {
    public int solution(int n, int a, int b)
    {
        return recursiveSolve(1,n,a,b);
    }

    public int recursiveSolve(int startNumber, int finishNumber, int playerA, int playerB){
        //둘 다 같은 위치에 포함 될 때
        if(inPlayer(startNumber,finishNumber,playerA) && inPlayer(startNumber,finishNumber,playerB)) {
            int partition = startNumber + (finishNumber - startNumber + 1)/2;
            int left = recursiveSolve(startNumber,  partition-1 , playerA, playerB);
            int right = recursiveSolve(partition,finishNumber,playerA,playerB);
            return left == -1 ? right : left;
        }
        //둘 다 포함되어있지 않을 때
        else if(!inPlayer(startNumber,finishNumber,playerA) && !inPlayer(startNumber,finishNumber,playerB))
            return -1;
        else{
            //다른 토너먼트로 포함되어있을 때
            int count = (finishNumber - startNumber + 1);
            int result = 0;

            //토너먼트 진행 횟수 계산
            while (count != 0){
                count /=2;
                result++;
            }
            return result;
        }
    }

    //구역에 플레이어가 존재하는지 확인
    public boolean inPlayer(int startNumber, int finishNumber, int player){
        return player >= startNumber && player <= finishNumber;
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)