[백준] 1158번: 요세푸스 문제

✏️ 개념 공부

 

요세푸스 순열 (Josephus permutation)

: 유대인 역사가 플라비우스 요세푸스가 겪은 경험을 바탕으로 만들어진 문제

 

 

문제 규칙

1. n명의 사람이 원형으로 앉아있다.
2. 첫 번째 사람부터 시작하여 k번째 사람을 제거한다.
3. 제거된 다음에는 그 다음 사람부터 다시 k번째 사람을 제거하는 과정을 반복 한 다.
4. 이렇게 해서 모든 사람이 제거될 때까지 계속한다.
5. 사람들의 제거 순서를 요세푸스 순열이라고 한다.

 

 

요세푸스 순열 구하는 방법

• 자료 구조 큐(Queue)를 사용하여 해결할 수 있다.
• 큐는 선입선출(First-In-First-Out, FIFO) 방식으로 동작하며, 사람들을 원형으로 배치하고 제거하는 과정을 큐에서 처리하는 방식이다.

 

 

 

---

🛠️ 문제 

1158번 요세푸스 문제

 

 

💡 풀이

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);

 

 

Algorithm-study/Algorithm/Solving/Stack & Que/1158.js at main · kwonboryong/Algorithm-study

 

 

---

💁‍♀️ 회고

처음 들어보는 개념이 많다.

요세푸스 순열이라는 걸 처음 알았고, 진행 방식이 이해가 안가서 펜으로 그려보고 간신히 이해했다.

 

문제 풀이 이전에 문제를 온전히 이해하는 능력이 필요하다는 걸 느꼈다.

 

 

1주차 - 2일 | Notion