💡문제 분석 요약

• 문제 설명
  • n명의 사람이 원형으로 앉아 있으며, k번째 사람을 순서대로 제거
  • 제거된 사람의 번호를 출력하고, 최종적으로 제거되는 순서를 구해야 함
• 출력 형식
  • 제거된 사람의 순서를 <x1, x2, x3, ..., xm> 형식으로 출력

💡알고리즘 설계

• 데이터 구조 선택
  • 구현 배열을 사용하여 큐 기능을 구현
• 큐 초기화:
  • 1부터 n까지의 숫자를 큐에 넣음
• 제거 과정:
  • 현재 큐의 길이가 0이 아닐 때까지 반복
  • k만큼 큐에서 요소를 꺼내고 다시 큐의 뒤에 추가 (사람을 순환시키는 과정)
  • k번째 사람을 제거하여 결과 배열에 추가
• 결과 출력
  • 최종적으로 저장된 제거 순서를 요구되는 형식으로 출력

💡코드

const fs = require('fs');
const path = require('path');

const input = fs.readFileSync(path.join(__dirname, 'input.txt')).toString().trim().split(' ');

// 입력값을 숫자로 변환
const n = parseInt(input[0], 10); // 총 인원
const k = parseInt(input[1], 10); // 제거할 사람의 순서

function solution(n, k) {
  const queue = []; // 총 인원 배열
  const answer = []; // 제거 순서 배열

  // 총 인원을 총 인원 배열에 넣음
  for (let i = 1; i <= n; i++) {
    queue.push(i);
  }

  // 제거 순서 카운터
  let count = 1;

  while (queue.length) {
    const shiftItem = queue.shift(); 
    // 큐에서 첫 번째 요소를 꺼냄

    if (count % k === 0) {
      // 현재 카운터 === 제거 순서라면 

      answer.push(shiftItem);
      //  k번째 사람을 제거 순서 배열에 추가
    } else {
      queue.push(shiftItem); 
      // k번째가 아닌 사람은 다시 총 인원 배열의 끝에 추가
    }

    count++;
    // 카운터 증가
  }

  // 형식대로 출력
  console.log(`<${answer.join(', ')}>`);
}

// 문제 풀이 함수 실행
solution(n, k);

💡시간복잡도

• 시간 복잡도: O(n * k)
  • n명의 사람에 대해 k번 반복하며, 큐에서의 삽입과 삭제가 O(1)인 경우에도 전체적으로 O(n * k)가 걸림
• 공간 복잡도: O(n)
  • 큐와 결과 배열을 저장하기 위한 공간이 필요함