[프로그래머스] 예상 대진표 (JAVA) (level2)

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

프로그래머스

---

문제 설명

△△ 게임대회가 개최되었습니다. 이 대회는 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 입니다.)

 

---

※ JAVA 코드 (예상 대진표)

import java.io.*;
import java.util.*;

class Solution
{
    public int solution(int n, int a, int b)
    {
        int answer = 0;
        int u, v;
        
        for(int i = 2; i <= n; i *= 2) {
            answer++;
            u = a / i;
            v = b / i;

            if(a % i == 0) u--;
            if(b % i == 0) v--;

            if(u == v) {
                return answer;
            }
        }

        return answer;
    }
}

---

※ 생각정리 (예상 대진표)

눈여겨 보여야 할것들

1) 자연수 범위 2의 20승까지 (완전탐색시 100% 시간초과)

2) 2의 지수 승만 주어진다 -> 범위의 축소 ( 반복문 2의 1승 ~ 2의 20승까지 총 최대 20번이면 충분히 해결가능 )

3) A와 B참가자는 무조건 승리한다는 조건

 

예상 대진표 문제를 풀기 위해서는 각 참가자가 어느 범위에 있는지를 파악해야한다.

예를 들어 [ 1, 2, 3, 4, 5, 6, 7, 8 ] 의 숫자 배열중 1, 2번 참가자가 언제 만날지를 탐색한다고 하였을때, 1과 2는 해당 숫자 배열을 2개씩 나눈 구간 [1, 2], [3, 4], [5, 6], [7, 8]의 구간 중 같은 2의 1승 구간에 포함되기 때문에 1번의 라운드만에 찾을 수 있다.

다음으로 같은 숫자배열중 3과 7의 참가자가 만나는 예를 들어보자. 먼저, 2개씩 나눈구간 [1, 2], [3, 4], [5, 6], [7, 8] 구간에는 해당 숫자 를 포함한 구간이 없다. 다음으로 2의 2승 구간인 4개씩 나눈구간을 볼때 [1, 2, 3, 4], [5, 6, 7, 8] 두 구간에도 3, 7이 같이 존재하는 구간은 찾을 수 없다. 마지막으로 숫자 2의 3승 구간인 8개 배열인경우 [1, 2, 3, 4, 5, 6, 7, 8] 에 두 숫자가 동시에 존재하므로 총 3라운드만에 두 숫자가 만날 수 있다.

 

위의 패턴으로 숫자 구간을 탐색할 수 있을때, 반복문의 시작을 2로 하고 2의 지수 승만큼 반복한다. 2, 4, 8, 16, 32, 64, 128 .... 의 각구간에 해당 두 수 A, B가 존재하는지 확인하기 위해 A, B에서 2의 지수 승을 나눈 몫을 구해 두 몫이 같으면 같은 지수 승 구간에 존재하게 된다. 이때 주의 할 점은 2의 지수 승인 수가 나누어 떨어지게 하는 수는 몫이 1더 크므로 -1을 해주어야한다. ( 1 / 2 = 0 | 2 / 2 = 1 )

 

- 새벽코딩 -