링크
https://school.programmers.co.kr/learn/courses/30/lessons/12985
문제 설명
(정답률 68%)
△△ 게임대회가 개최되었습니다. 이 대회는 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 |
나의 코드
class Solution {
public int solution(int n, int a, int b) {
int answer = 1; //a와 b가 최소 한 번은 만나기 때문에 1로 초기화
//n은 2의 거듭제곱이고 라운드가 거듭제곱 횟수 만큼 진행되므로
//for문을 다음과 같이 구성
for (; n > 0; n /= 2) {
//a와 b가 만날때는 a와 b의 차가 1이여야 하고
//둘 중 큰 수가 짝수여야 한다
//a와 b가 2, 3이라면 라운드가 한 번 더 진행되어야 한다
if (Math.abs(a - b) == 1 && Math.max(a, b) % 2 == 0) {
break;
}
//다음 라운드 번호 계산
if (a % 2 != 0) {
a += 1;
}
if (b % 2 != 0) {
b += 1;
}
a /= 2;
b /= 2;
answer++;
}
return answer;
}
}다른 사람의 풀이
class Solution {
public int solution(int n, int a, int b) {
int round = 0;
while (a != b) {
a = a / 2 + a % 2;
b = b / 2 + b % 2;
round++;
}
return round;
}
}정리
푸는데 40분쯤 걸린거 같다.
처음에는 while문을 써서 a와 b의 차이가 1이 될때까지로 계산을 했으나
a=2, b=3일 경우도 해당이 되어 버려서 둘중 최댓값이 짝수여야 한다는 조건도 추가했으나
도저히 풀리지 않아서..
N이 2의 거듭제곱 수로 주어지는 것을 보고 for문으로 변경하여 풀이 하였다.
채점을 하였는데 계속 테스트 1번이 통과되지 않았는데..
a + b = 3일때가 문제였다. 라운드가 한 번만 진행될때가 있기 때문에
if문의 위치를 맨 위로 수정하였다.
