[알고리즘 문제] programmers - 예상 대진표

 

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

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

문제는 단순 구현문제인 것 같다. 문제를 처음 접했을 때, 어떻게 풀지? 라는 생각을 했는데 조금 생각하니 간단한 문제였다

 

토너먼트 식으로 진행되는 경기에서 두 팀은 몇번째 경기만에 붙게 되는지를 출력하는 문제이다, 여기서 조건으로 두 팀은 무조건 경기에서 이긴다는 것을 가정한다.

 

예를 들어 1,2,3,4,5,6,7,8팀이 있다면 4번팀과 7번팀이 몇번째 만에 붙게되는지 확인해보면 첫번쨰 경기는 1-2, 3-4, 5-6, 7-8경기에서 붙게 된다. 4번의 경기에서 각 이긴팀에게 1,2,3,4로 다시 번호르 부여해준다. 여기서 기존의 4번팀은 2번으로(3-4경기에서 이겼으므로), 7번팀은 4번으로 번호를 부여해준다. 다시 1-2, 3-4팀이 경기를 붙고 이긴팀에 대하여 1,2번호가 주어진다. 4,7번팀은 무조건 이긴다고 했으니 결국에는 마지막에 1,2번 팀은 처음의 4,7번 팀이였으므로 3번 만에 경기를 붙게된다.

 

1  2  3  4  5  6  7  8     

 1        [2]    3    [4]    - 1번

      1                2        - 2번

              1                  - 3번

 

아이디어는 한 경기를 진행할 때 마다 a와 b의 값을 1/2 해줍니다. 1/2한 값에 1을 더해줍니다. 7-8팀이 경기하게 되면 7이든 8이든 다음 경기에서 4번의 숫자를 부여받게 됩니다. 하지만 8의 경우는 1/2해주면 4가 되지만 7의 경우는 3이 됩니다. 그렇기 때문에 값이 홀수인 경우는 1을 더해주게 됩니다. 이런 방법으로 두 팀의 차가 1이 날때까지 반복하면 됩니다.

 

 

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