프로그래머스 코딩테스트 연습 Level 2 - 예상 대진표 (JavaScript)

프로그래머스 코딩테스트 연습 Level 2 - 예상 대진표 (JavaScript)

 

 

Programmers(프로그래머스)의 코딩테스트 연습문제 Level 2 중,

[예상 대진표] 문제를 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 : 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 하면 됩니다.

 

 

작성한 답

solution.js

function solution(n, a, b) {
    let answer = 0;
    while (a !== b) {
        a = Math.ceil(a / 2);
        b = Math.ceil(b / 2);
        answer++;
    }
    return answer;
}

 

설명

처음에는 이런 저런 조건들을 여러가지 생각하며 문제를 해결하려고 했었습니다.

반복문을 돌며 1과 2, 3과 4, 5와 6 등 큰 번호와 작은 번호의 차이가 1이어야 하며 작은 번호가 홀수, 큰 번호가 짝수여야한다 등의 조건을 걸었었는데 그러한 조건문을 걸다보니 시간초과가 발생했습니다.

 

하지만 문제를 조금 더 이해하다보니 그러한 조건문은 전혀 필요 없이 계속해서 각 참가자들의 번호를 맞게 설정시키다보면 결국 같은 수에 도달하는 것을 알게되었습니다.

예시에 나온 N = 8, A = 4, B = 7 에서 설명해드리자면 

1. 첫번째 반복문에서 A와 B는 다음 라운드의 번호인 A는 2가 되고 b는 4가 됩니다. 라운드 수는 1이 됩니다.
2. 두번째 반복문에서 A와 B는 다음 라운드의 번호인 A는 1가 되고 b는 2가 됩니다. 라운드 수는 2가 됩니다.
3. 세번째 반복문에서 A는 1가 되고 b도 1이 됩니다. A와 B가 같아지면 이 전 반복문의 상황에서 1과 2, 3과 4 등 맞붙는 상황이었다는 말과 같습니다. 만약 이전 반복문에서 A가 2고 B가 3인 상황이었다면 이번 반복문에서 A가 1, B가 2가 됐을것이고 그럼 또 반복문이 한번더 돌게 될것입니다. 즉 같은 숫자가 될 때 까지 반복하는 것으로 앞서 말했던 작은 번호가 홀수, 큰번호가 짝수 이런 조건문은 사용할 필요가 없다는 말이 됩니다. 라운드 수를 0에서 시작했기에 이번 반복문에서 1 더해진 라운드 3이 정답이 됩니다.

 

 

 

도움이 되셨다면 공감, 댓글 부탁드립니다!

궁금하신 점이나 요청사항은 언제든지 말씀해주세요!

피드백도 언제나 환영입니다!

 

감사합니다.