문제

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

N	A	B	answer
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 하면 됩니다.

나의 코드 (+3점)

function solution(n,a,b){
    let players = [...Array(n)].map((_,i)=> i + 1);
    let [g1, g2] = [players.slice(0, players.length / 2), players.slice(players.length / 2)];
    while(true){
        if(g1.includes(a) && g2.includes(b) || g1.includes(b) && g2.includes(a)) break;
         else if(g1.includes(a) && g1.includes(b) ){
            players = g1;
            [g1, g2] = [players.slice(0, players.length / 2), players.slice(players.length / 2)];
        } else {
            players = g2;
            [g1, g2] = [players.slice(0, players.length / 2), players.slice(players.length / 2)];
        }
    }
  const playersL = [g1, g2].flat().length;
    return Math.log2(playersL);
}

뭔가 반복되는 게 많군 ㅋㅋㅋㅋ 하지만 어쩔 수 없다 이걸 풀 당시엔 두뇌 풀가동을 해서 생각해낸 유일한 풀이였던 거슬,,
내가 생각했던 방향은 다음과 같다.
대진표를 반으로 두 그룹으로 쪼갰을 때 앞의 그룹을 그룹1이라 하고 뒤의 그룹을 그룹2라고 한다면, a와 b가 둘다 그룹1에 있거나 둘 다 그룹2에 있으면 나머지 그룹은 없는 셈 쳐도 답이 달라지지 않는다.
그래서 a와 b가 서로 다른 그룹에 있을 때까지 while문을 이용하여 그룹을 계속 반으로 쪼갰다. (서로 다른 그룹에 있을 경우 반복문 탈출)
그렇게 하면 제한사항에서 경기자 수가 2의 지수승으로 주어진다고 했기 때문에 경기자 수에 밑이 2인 로그를 씌우면 답이 나온다.
자신없이 제출했지만 일단 통과는 했다 ㅋㅋㅋㅋㅋ
오늘부터 점수 적기로 했으니 기록하자면 3점!!받았다. 나름 선방???

그리고 백준 silver4에서도 토너먼트 문제가 있어서 한번 풀어봤는데
맙소사 이번에는 경기자수가 2의 지수승이 아니네?

일단 문제부터 적자면

문제

김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다.

마침 이 스타 대회에 임한수도 참가했다. 김지민은 갑자기 스타 대회에서 우승하는 욕심은 없어지고, 몇 라운드에서 임한수와 대결하는지 궁금해졌다. 일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다. 1 라운드에서 김지민의 번호와 임한수의 번호가 주어질 때, 과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.

입력
첫째 줄에 참가자의 수 N과 1 라운드에서 김지민의 번호와 임한수의 번호가 순서대로 주어진다. N은 2보다 크거나 같고, 100,000보다 작거나 같은 자연수이고, 김지민의 번호와 임한수의 번호는 N보다 작거나 같은 자연수이고, 서로 다르다.

출력
첫째 줄에 김지민과 임한수가 대결하는 라운드 번호를 출력한다. 만약 서로 대결하지 않을 때는 -1을 출력한다.

예제 입력 1

16 1 2

예제 출력 1

1

예제 입력 2

16 8 9

예제 출력 2

4

예제 입력 3

1000 20 31

예제 출력 3

4

예제 입력 4

65536 1000 35000

예제 출력 4

16

예제 입력 5

60000 101 891

예제 출력 5

10

시간 초과 났던 코드

let input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ");

const a = Number(input[1]);
const b = Number(input[2]);

let pow2 = 2;
while (pow2 < b) {
  pow2 *= 2;
}

let players = [...Array(pow2)].map((_, i) => i + 1);
let [g1, g2] = [
  players.slice(0, players.length / 2),
  players.slice(players.length / 2),
];
while (true) {
  if ((g1.includes(a) && g2.includes(b)) || (g1.includes(b) && g2.includes(a)))
    break;
  if (g1.includes(a) && g1.includes(b)) {
    players = players.slice(0, players.length / 2);
    [g1, g2] = [
      players.slice(0, players.length / 2),
      players.slice(players.length / 2),
    ];
  } else {
    players = players.slice(players.length / 2);
    [g1, g2] = [
      players.slice(0, players.length / 2),
      players.slice(players.length / 2),
    ];
  }
}
const answer = Math.log2([g1, g2].flat().length);
console.log(answer);

좋았어 프로그래머스 통과했으니 같은 논리로 밀어붙여!!
그리고 시간 초과로 사망

두 명이 서로 다른 그룹에 있을 때까지 쪼개는 논리를 적용할 수 있을 것이라고 생각했던 이유는
a,b 중 더 큰 수보다는 크지만 가장 가까운 2의 지수승으로 player 수를 늘리면 답이 똑같아진다고 생각했기 때문이다. (정확하지는 않지만 노트에 끄적여본 뇌피셜에 의하면 그렇다..))
그런 다음 밑이 2인 로그를 씌우면 되지 않나?
하지만 시간 초과가 되었는 걸..

결국 다른 코드를 참고하여 제출했더니 겨우 통과했다.

let input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ");

let [kim, lim] = [Number(input[1]), Number(input[2])];
let count = 0;
while (kim !== lim) {
  kim = Math.ceil(kim / 2);
  lim = Math.ceil(lim / 2);
  count++;
}
console.log(count);

이런 논리를 사용할 수 있을지는 꿈에도 몰랐다 흑흑

          (1         2)       //4라운드
     (1          2)     3     //3라운드
 (1     2)   (3     4)  5     //2라운드
(1 2) (3 4) (5 6) (7 8) 9     //1라운드

만약 a = 8, b = 9라면
다음라운드에 이겨서 올라가면 짝수인 player는 절반이 되고, 홀수는 절반의 올림 숫자가 되므로,
a: 8 -> 4 -> 2 -> 1
b: 9 -> 5 -> 3 -> 2
4라운드가 끝나면 이미 두 숫자가 while문을 돌면서 같아지기 때문에 답이 4가 되는 것이다.

그룹을 2개로 쪼개고 돌리고 할 필요가 없었던 것이었다.. 하하하...
라운드 별로 숫자가 변하는 패턴을 좀 더 탐구했다면 떠오를 수도 있었을까??
더 많이 문제를 풀어봐야겠다 화이팅!!