[백준] 요세푸스 문제 #1158

설명

입력의 범위가 5000으로 작기 때문에 JS의 배열을 queue로 생각하고 풀면 되지만 배열에서 shift 연산자를 쓰는 것에 비용이 크다고 판단해서 자료구조 연습겸 Circular Linked List를 이용해 풀었다.

그렇다고 일반적인 Circular Linked List는 또 아닌게 문제 요구사항에 맞게 필요한 함수만 구현하고 또 removeAt함수에서는 this.tail = target이라는 값을 줘서 다음 반복을 위해 지울 노드를 tail로 설정해주었다.

다른 사람의 풀이를 보니 그냥 queue를 써도 좋아보이는데 JS는 queue가 없으니.. 차라리 Linked-List로 Queue를 만들고 pop, push 함수만 구현해서 사용해도 좋을 것 같다.

(그래서 c++은 queue로 풀었다.)

Node.js 풀이

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
// test
// const input = `7 3`.trim().split('\n');
const [N, K] = input[0].split(' ').map(Number);

class Node {
  value;
  next;
  constructor(value) {
    this.value = value;
  }
}

class CircularLinkedList {
  constructor() {
    this.size = 0;
    this.tail = null;
  }
  insert(data) {
    const newNode = new Node(data);
    if (this.size === 0) {
      this.tail = newNode;
      this.tail.next = newNode;
    } else {
      newNode.next = this.tail.next;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size += 1;
  }
  removeAt(index) {
    let cur = this.tail;
    let cnt = index - 1;
    while (cnt--) cur = cur.next;
    const target = cur.next;
    cur.next = cur.next.next;
    const value = target.value;
    this.tail = target; // 다음 반복을 위해 지울 노드를 tail로 선정
    this.size -= 1;
    return value;
  }
}

const solution = (N, K) => {
  const answer = [];
  const cll = new CircularLinkedList();
  for (let i = 1; i <= N; i++) cll.insert(i);
  let k = K;
  while (N--) {
    answer.push(cll.removeAt(k));
  }
  return `<${answer.join(', ')}>`;
};

console.log(solution(N, K));

C++ 풀이

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, K;
    cin >> N >> K;
    queue<int> Q;
    for (int i=1; i<=N; i++) Q.push(i);
    cout << "<";
    while(true) {
        int cnt = 0;
        for (int i=1; i<K; i++) {
            Q.push(Q.front());
            Q.pop();
        }
        cout << Q.front();
        Q.pop();
        if (!Q.empty()) cout << ", ";
        else break;
    }
    cout << '>';
    return 0;
}

문제링크

https://www.acmicpc.net/problem/1158