[프로그래머스] N진수 게임

N진수 게임 풀이

문제 파악

N진수 게임의 규칙을 정리하면:

• 0부터 시작해서 n진법으로 말하기
• m명이 돌아가면서 각 자릿수를 말함
• 내 차례(p번째)일 때만 답에 저장
• 총 t개까지 구하기

풀이 흐름

1단계: 게임 진행 방식 이해

n=2, m=2, p=1인 경우:

숫자: 0 → "0" → 차례1(나) → 답: "0" 
숫자: 1 → "1" → 차례2(상대) → 답 변화 없음
숫자: 2 → "10" → 차례1(나),차례2(상대) → 답: "01"
숫자: 3 → "11" → 차례1(나),차례2(상대) → 답: "011"  
숫자: 4 → "100" → 차례1(나) → 답: "0111"

2단계: 구현 방향

function solution(n, t, m, p) {
  let num = 0;        // 현재 숫자
  let turn = p;       // 내 차례번호  
  let result = '';    // 내 답

  while (result.length < t) {
    const converted = num.toString(n);  // n진법 변환

    for (let digit of converted) {
      if (turn === p) result += digit;   // 내 차례면 저장

      turn = (turn % m) + 1;             // 차례 순환

      if (result.length >= t) break;
    }
    num++;
  }

  return result.toUpperCase();
}

3단계: 핵심 로직

차례 관리

turn = (turn % m) + 1;  // 1→2→3→...→m→1 순환

조기 종료

if (result.length >= t) break;  // 최적화

시간 복잡도

• O(t × log n)
• 각 숫자마다 최대 log n 자릿수 확인

주의사항

1. 문자 변환: 10진수 이상일 때 소문자 → 대문자 변환 필요
2. 차례 초기화: 내 차롮가 p번이므로 초기값 p로 설정
3. 0부터 시작: 첫 숫자는 자연수 0

이 문제는 실제 게임을 시뮬레이션하면 되는 구현 문제다. 진법 변환과 순환 큐 개념만 알면 쉽게 풀 수 있다.