[Baekjoon] 11866 - 🔗요세푸스 문제 0

😀문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

---

😁입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

---

😂출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입력 1 
7 3
예제 출력 1 
<3, 6, 2, 7, 5, 1, 4>

---

🤣출처

• 문제를 만든 사람: baekjoon

---

😃알고리즘 분류

• 구현
• 자료 구조
• 큐

---

😄나의풀이

분류 자체가 스택, 큐, 덱(Deque) 이라 그나마 어울리는 덱 자료구조로 썼지만, 이 문제는 원형 연결 리스트 자료 구조로 풀이하는게 가장 이상적이라 생각한다. 아쉬움이 많이 남는 문제

class Node {
    left = undefined
    right = undefined
    constructor(val, idx) {
        this.value = val
        this.idx = idx
    }
}

class Deque {
    position = undefined
    size = 0
    nodes = []
    constructor(limit) {
        this.limit = limit
    }
    insert(val, idx) {
        const curNode = new Node(val, idx)
        if(!this.position) this.position = curNode
        this.nodes.push(curNode)
        this.size += 1
        if(idx === 0) return
        const prevNode = this.nodes[idx-1]
        if(idx === this.limit-1) {
            curNode.right = this.nodes[0]
            this.nodes[0].left = curNode
        }
        curNode.left = prevNode
        prevNode.right = curNode
    }
    pop(num) {
        let curNode = this.position
        const idx = this.size === this.limit ? 1 : 0
        for(let i = idx ; i < num ; i ++) {
            curNode = curNode.right
        }
        const val = curNode.value
        if(curNode?.left) curNode.left.right = curNode?.right
        if(curNode?.right) curNode.right.left = curNode?.left
        this.position = curNode
        this.size -= 1
        return val 
    }
}

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split(" ")
const [N, K] = input.map(a => Number(a))
const result = []
const deque = new Deque(N)
for(let i = 1 ; i <= N ; i ++) {
    deque.insert(i, i-1)
}
while(deque.size) {
    const popedItem = deque.pop(K)
    result.push(popedItem)
}

console.log(`<${result.join(", ")}>`)