Programmers | Level 2 | 예상 대진표

Programmers | Level 2 | 예상 대진표

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Simulation

Description

△△ 게임대회가 개최되었습니다. 이 대회는 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번 참가자와 몇 번째 라운드에서 만나는지 반환하는 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

Constraints

• N: 2의 지수 승으로 주어지며, 21 이상 220 이하인 자연수입니다.
• A, B: N 이하인 자연수이며, A ≠ B입니다.

Examples

N	A	B	answer
8	4	7	3

Solutions

• ⏳ TC: O(log N)
• 💾 SC: O(1)

import java.util.*;

class Solution {
    public int solution(int n, int a, int b) {
        int round = 0;
        while (a != b) {
            a = (a + 1) / 2;
            b = (b + 1) / 2;
            round++;
        }
        return round;
    }
}

Approaches

이 문제는 토너먼트 형식의 시뮬레이션을 통해 두 참가자가 몇 번째 라운드에서 만나는지를 계산하는 문제입니다. 두 참가자가 게임을 이기면서 다음 라운드로 진출할 때마다 번호가 갱신됩니다.

토너먼트에서 다음 라운드로 진출한 참가자의 번호는 다음과 같이 갱신됩니다:

• 각 라운드에서 1번과 2번이 붙으면, 승자는 다음 라운드에서 1번이 됩니다.
• 3번과 4번이 붙으면, 승자는 다음 라운드에서 2번이 됩니다.
• 5번과 6번이 붙으면, 승자는 다음 라운드에서 3번이 됩니다.
• ...

이 규칙을 일반화하면, 현재 라운드에서 번호 k를 가진 참가자가 다음 라운드로 진출할 때의 번호는 (k + 1) / 2가 됩니다.

문제를 해결하기 위해 다음과 같은 접근 방식을 사용합니다:

• currentA와 currentB가 같아질 때까지 다음 라운드로 진출합니다.
• 각 라운드마다 두 번호를 (번호 + 1) / 2로 갱신합니다.
• 라운드 카운트를 증가시킵니다.
• 두 번호가 같아졌을 때의 라운드 카운트를 반환합니다.

이 알고리즘의 시간 복잡도는 각 라운드마다 번호를 갱신하는 데 상수 시간이 걸리므로 O(log N)입니다. 공간 복잡도는 추가적인 메모리를 거의 사용하지 않으므로 O(1)입니다.

Attempts

처음에는 이 문제의 규칙을 찾지 못해 어려움을 겪었습니다. 시뮬레이션 문제는 주로 주어진 상황을 모의 실험하고 규칙을 발견하여 문제를 해결하는 것이 핵심입니다. 이 문제에서도 토너먼트의 규칙을 이해하고, 각 라운드마다 참가자의 번호가 어떻게 변화하는지를 파악하는 것이 중요했습니다. 다양한 시뮬레이션 문제를 풀어보면서 이러한 규칙을 빨리 발견하고 적용하는 능력을 키워야 할 것입니다.

시뮬레이션 문제는 주로 복잡한 시스템의 상태 변화를 모의 실험을 통해 해결하는데, 이를 위해 다양한 시뮬레이션 문제를 풀어보면서 익숙해지는 것이 필요합니다. 앞으로도 더 많은 문제를 접하면서 이러한 규칙을 빨리 발견하고 효율적으로 문제를 해결할 수 있도록 연습이 필요합니다.