essential
essential

15. Josephus

링크드 리스트와 스택을 활용해 대량 데이터의 삭제, 복원, 이동 작업을 효율적으로 처리하는 설계 이해

algorithm test

15. Josephus

Sunhyup Lee. (2024). To be a successful candidate for the coding test. goldenrabbit. p.173.

Problem solving

1. Queue를 이용하여 풀기

algorithm solving strategy

Queue solving

Jay Tak

class Queue {
  items = [];
  front = 0;
  rear = 0;

  push(item) {
    this.items.push(item); // 수정: this.items로 오타 수정
    this.rear++;
  }

  size() {
    return this.rear - this.front;
  }

  pop() {
    return this.items[this.front++]; // front 값 증가
  }
}

function solution(N, K) {
  const queue = new Queue();

  // 1부터 N까지 큐에 삽입
  for (let i = 1; i <= N; i++) {
    queue.push(i);
  }

  // 요제푸스 알고리즘 수행
  while (queue.size() > 1) {
    // K-1번 pop하고 push
    for (let i = 0; i < K - 1; i++) {
      queue.push(queue.pop());
    }
    // K번째 원소 제거
    queue.pop();
  }

  // 마지막 원소 반환
  return queue.pop();
}

console.log(solution(5, 2)); // 출력: 3




Development
Algorithm