(Java) Programmers 예상 대진표

 

 

- 목차

 

소개.

"프로그래머스의 예상 대진표 문제" 의 웹링크입니다.

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

프로그래머스

 

 

 

문제 분석.

모든 참여자들은 토너먼트 형식의 승부를 합니다.

한 대진에서 2명의 참여자가 승부를 하고, 한 명만이 다음 라운드에 참여할 수 있습니다.

이를 구현하기 위해서 Queue 를 사용합니다.

Queue 에서 2명씩 poll 하여 한명을 다시 add 합니다.

다만, a 와 b 는 반드시 승리하기 때문에 a 또는 b 는 반드시 다시 add 되어야합니다.

 

그리고 1 라운드 도중에 살아남은 참여자의 수는 N/2 보다 크고, N 명보다 같거나 작아야합니다.

예를 들어, 8명의 참가자는 최종적으로 4명으로 줄게 됩니다.

그래서 1라운드에선 4 명보다 크고 8명 보다 작거나 같은 참여자가 존재합니다.

 

알고리즘 구현.

import java.util.*;

class Solution
{
    public int solution(int n, int a, int b)
    {
        int answer = 0;
        // 2의 지수를 구합니다. 
        // 8 -> 3, 4 -> 2, 2 -> 1, 1 -> 0
        int exponent = getExponent(n);
        
        // a 와 b 의 대소관계가 명시되지 않기 때문에 큰 값과 작은 값을 구합니다. 
        int minMember = Math.min(a, b);
        int maxMember = Math.max(a, b);
        Queue<Integer> queue = new LinkedList();
        
        // 초기화
        // queue 는 토너먼트에 참가하는 모든 참여자를 대전순서대로 추가합니다. 
        for (int i = 1; i <= n; i++) {
            queue.add(i);
        }
        
        // 2개의 참여자를 poll 하고 승자를 다시 add 합니다. 
        // a 와 b 는 반드시 승리합니다. 
        while (true) {
            Integer member1 = queue.poll();
            Integer member2 = queue.poll();
            // 두 멤버가 a 와 b 인 경우에 반복문을 종료합니다. 
            if (member1 == minMember && member2 == maxMember) break;
            
            if (member1 == a || member2 == a) {
                queue.add(a);
            } else if (member1 == b || member2 == b) {
                queue.add(b);
            } else {
                // 아무 참여자를 추가합니다. 
                queue.add(member1);
            }
        }
        
        if (queue.isEmpty()) {
            return exponent;
        }
        
        while (true) {
            double min = Math.pow(2, exponent - answer - 1);
            double max = Math.pow(2, exponent - answer);
            
            if (queue.size() + 2 > min && queue.size() + 2 <= max) {
                break;
            }
            answer++;
        }
        return answer + 1;
    }
    
    int getExponent(int n) {
        return (int) (Math.log(n) / Math.log(2));
    }
}