리액트 심화 프로젝트 (5)

신나는 알고리즘 풀이 시간. 

오늘 풀어본 문제는 토너먼트 방식의 게임에서 두 참가자가 몇 라운드에서 만나는지 구하는 알고리즘 문제였다.
단순한 반복 계산 문제 같아 보였지만, 예외 상황을 고려하지 않아 초기에 오답을 내기도 했다.
이번 글에서는 문제 풀이 과정과 함께, 오답 원인과 올바른 풀이를 정리해보았다.

문제 설명

게임의 진행 방식

1. N명의 참가자가 토너먼트 방식으로 겨룬다.
2. 1번↔2번, 3번↔4번, ..., N-1번↔N번으로 매칭.
3. 각 게임의 승자는 다음 라운드로 진출하며, 새로운 번호를 부여받는다.
   • 승자의 번호는 Math.ceil(현재 번호 / 2)로 계산.
4. 게임은 한 명이 남을 때까지 계속된다.

문제 목표

참가자 A와 경쟁자 B가 몇 번째 라운드에서 만나는지를 계산하라.

제한사항

• N: 21 이상 220 이하 (2의 지수승으로 주어짐)
• A, B: 서로 다른 번호, N 이하의 자연수

1.  

오답노트

초기 오답 코드

function solution(n, a, b) {
  let answer = 0;
  while (Math.abs(a - b) !== 1) { // 서로 번호가 1 차이일 때 종료
    if (a % 2 === 0) {
      a = a / 2;
    } else {
      a = (a + 1) / 2;
    }
    if (b % 2 === 0) {
      b = b / 2;
    } else {
      b = (b + 1) / 2;
    }
    answer++;
  }
  answer += 1; // 라운드 수 보정
  return answer;
}

오답 이유

1. 종료 조건이 부정확
   • Math.abs(a - b) !== 1은 두 번호의 차이가 1일 때 종료를 기대.
   • 하지만 A와 B가 반드시 인접 번호일 필요는 없다.
     • 예: A=4, B=5일 경우, 서로 다른 상대와 대결하므로 이 조건은 부적절.
2. 복잡한 번호 갱신 로직
   • A와 B의 번호를 짝수와 홀수로 구분해 갱신.
   • 그러나, 승자의 번호는 단순히 Math.ceil(현재 번호 / 2)로 계산 가능.
     • 불필요한 조건문으로 코드가 복잡해짐.

풀이 과정

1. 라운드 진행

• A와 B의 번호가 같아질 때까지 반복.
• 각 라운드에서 두 번호를 Math.ceil(현재 번호 / 2)로 갱신.

2. 종료 조건

• A와 B가 같은 번호를 부여받으면, 해당 라운드에서 두 참가자는 대결하게 됨.

3. 라운드 수 계산

• 라운드가 진행될 때마다 answer를 증가시켜 몇 번째 라운드인지 기록.

정답 코드 설명

코드

function solution(n, a, b) {
  let answer = 0;

  // A와 B가 같아질 때까지 반복
  while (a !== b) {
    // 다음 라운드 번호 계산
    a = Math.ceil(a / 2);
    b = Math.ceil(b / 2);
    answer++;
  }

  return answer;
}

 

과정

1. 초기화
   • answer: 라운드 수를 기록 (초기값 0).
2. 반복문
   • A와 B가 같은 번호가 될 때까지 while (a !== b) 반복.
3. 번호 갱신
   • Math.ceil(현재 번호 / 2)로 다음 라운드 번호를 계산:
     • 승자는 이전 번호의 절반을 올림 처리한 값.
4. 결과 반환
   • A와 B가 대결하게 되는 라운드 수(answer) 반환.

배운 점

1. 종료 조건의 중요성

• 문제의 규칙을 정확히 이해하고, A와 B가 대결 상대가 되는 명확한 종료 조건을 설계해야 한다.

2. 불필요한 조건 제거

• 승자 번호 계산은 짝수/홀수 조건 없이 Math.ceil(현재 번호 / 2)로 간단히 해결 가능.

3. 반복 구조 활용

• 문제를 단순히 반복하며 계산하더라도, 종료 조건이 명확하다면 효율적으로 풀이 가능.