2017 팁스타운 - 예상 대진표 (python & JavaScript)

프로그래머스에서 제공하는 연습 문제를 옛날 자료부터 최근 자료까지 모두 풀고 있습니다.

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

---

문제 설명

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

이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

제한사항

• N : 2^1 이상 2^20 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
• A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

입출력 예

입출력 예 설명

입출력 예 #1
첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.

 

✍️ 풀이

문제를 보면 토너먼트를 통해 우리는 이진 트리와 같은 형태가 생각날 것이다. 이러한 모양을 볼 때 이진 탐색을 하면 좋을 거 같다는 생각을 했다. 그래서 작성한 코드가 다음과 같다. 

JavaScript를 이용한 풀이

function solution(n,a,b)
{
    const FindLevel = (players, a, b) => {
        let tmp = players.slice()
        let level = 0
        while (true){
            let mid = tmp.length / 2
            let leftPlayers = tmp.slice(0, mid)
            let rightPlayers = tmp.slice(mid)
            if(leftPlayers.includes(a) && leftPlayers.includes(b)) {
                tmp = leftPlayers.slice()
                level += 1
            } else if (rightPlayers.includes(a) && rightPlayers.includes(b)){
                tmp = rightPlayers.slice()
                level += 1
            } else return level
        }
    }
    var answer = 0;
    for (let i = 1; i < 21; i++) if (2 ** i === n) {answer = i; break}
    players = Array.from({length : n}, (v, i) => i + 1)
    answer -= FindLevel(players, a, b)
    
    return answer;
}

python을 이용한 풀이

def binarySearch(player, a, b):
    temp = player
    level = 0
    while True:
        mid = len(temp) // 2
        leftTemp = temp[:mid]
        rightTemp = temp[mid:]
        if a in leftTemp and b in leftTemp:
            temp = leftTemp
            level += 1
        elif a in rightTemp and b in rightTemp:
            temp = rightTemp
            level += 1
        else:
            return level
        
def solution(n,a,b):
    answer = 0
    temp = [i for i in range(1, n + 1)]
    for i in range(1, 21):
        if n == 2 ** i:
            answer = i
            break
    answer -= binarySearch(temp, a, b)

    return answer

먼저 answer에 루트까지 갈 경우의 모든 라운드 수를 담는다. 이는 n의 지수가 몇인지를 확인하면 된다. 예제에 n가 8인 경우 총 2^3인 3라운드만 지나면 루트까지 갈 수 있다. 이후에 이진 탐색으로 위에서부터 리스트를 분할하면서 탐색해서 내려오면 된다. 나눌 때는 우리가 찾는 a, b의 값이 한쪽(left, right)으로 모여 있는지 확인을 통해 내려오면 되고 만약 두 값이 나눠지는 경우, 우리가 찾는 두 player가 경기를 하는 순간이다.

 

 

정리

이진탐색을 할 때 start와 end를 둬서 탐색을 통해 index를 가져오는 경우가 일반적인데 위와 같이 리스트를 나눠서 루트에서 얼마나 내려가는지에 대한 level을 찾을 수도 있다는 사실을 알고 사용할 수 있어야겠다.🤔