프로그래머스 - 예상 대진표

문제 설명

△△ 게임대회가 개최되었습니다. 이 대회는 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 : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
• A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

---

입출력 예

NABanswer

8

4

7

3

입출력 예 설명

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

 

나의 풀이(틀린 풀이)

import math


def solution(n, a, b):
    answer = int(math.log2(n))  # 지수의 크기가 곧 최대 라운드 수
    if a > b:  # a가 더 작은수로 만든다.
        a, b = b, a

    if a % 2 == 1 and b == a + 1:  # a가 홀수이고 a,b 가 연속 된 수일 때는 바로 경기
        return 1

    for _ in range(answer):
        mid = n // 2
        print(mid, n)
        if a <= mid and b > mid:  # 가운데를 기준으로 떨어져 있다면
            return answer

        elif a > mid:  # 둘 다 중간 보다 위에 있다면
            n = (mid + 1) + n
            # print(n)

        elif b <= mid:  # 둘 다 중간보다 아래
            n = mid
            # print(n)

        answer -= 1

    return answer


print(solution(16, 9, 12))

마지막 프린트 케이스가 예외 케이스이다. 내가 접근한 풀이는 중간값을 구해서 그 값에 따라 세가지 경우가 나뉜다. 

1) 두 수가 중간 값을 기준으로 떨어져 있을 때

2) 두 수가 중간 값을 기준으로 왼쪽에 있을 때 (두 수 중 큰값이 중간값보다 작은 경우)

3) 두 수가 중간 값을 기준으로 오른쪽에 있을 때 (두 수 중 작은 값이 중간값보다 큰 경우)

 

1번 경우에 바로 answer를 리턴하면 된다. answer는 최종 라운드 수이고, 점차 라운드를 빼주는 식으로 접근했다. 중간 값을 기준으로 떨어진 순간이 최종 라운드가 되기 때문.

 

2, 3번의 경우 지속적으로 중간값을 갱신 시켜주면 된다. 여기서 문제가 발생했다. 마지막 elif에서 n = mid 라고 중간값을 업데이트 해주었는데, 최댓값만 있고 최소값은 없다. 

이 말은 즉, 중간값이라 하믄 제일 작은 값과 가장 큰값의 중간값이라는 건데 한가지 값만 정의해줬다는 것이다. 따라서 중간값을 갱신하는 문제에선 투포인트로 접근해야하는 것을 기억하자!!!

 

투포인트 접근 풀이

import math


def solution(n, a, b):
    answer = int(math.log2(n))  # 지수의 크기가 곧 최대 라운드 수
    if a > b:  # a가 더 작은수로 만든다.
        a, b = b, a

    if a % 2 == 1 and b == a + 1:  # a가 홀수이고 a,b 가 연속 된 수일 때는 바로 경기
        return 1

    left = 1
    right = n
    for _ in range(answer):
        mid = (left + right) // 2
        if a <= mid and b > mid:  # 가운데를 기준으로 떨어져 있다면
            return answer

        elif a > mid:  # 둘 다 중간 보다 위에 있다면
            left = mid + 1
            right = right

        elif b <= mid:  # 둘 다 중간보다 아래
            left = left
            right = mid

        answer -= 1

    return answer

투포인트 접근 법을 통해 left, right로 다시 접근해서 풀었다. 2번의 경우 두 수가 중간 값보다 위에 있다면 left만 갱신! 3번의 경우 두 수가 중간값보다 작은 경우 right 만 갱신! 이렇게 mid를 갱신하는 작업을 하니 생각한대로 잘 결과가 나왔다.

 

다른 사람의 풀이도 좋은 풀이가 많지만 내가 접근한 풀이대로 블로깅하여 정리하고 싶었다! 

 

** 중간값을 갱신하여 접근하는 방식은 투포인트로 접근해서 풀자!