[백준] 11866. 요세푸스 문제 0

---

문제

 

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

11866번: 요세푸스 문제 0

 

 1부터 N까지의 사람이 원을 그리고 앉아 있을 때 K번째 사람을 순서대로 뽑는 문제

 

---

전략

 

01. LinkedList

 처음 생각한 풀이는 사람이 순서대로 앉아 있기 때문에 Singly Linked List로 풀 수 있지 않을까였다. 인덱스를 K만큼 증가시켜가며 뽑은 뒤 범위는 넘는다면 N로 나눈 나머지를 다시 인덱스로 함으로서 범위 내에서 계속 돌도록 유지할 수 있다. 결과적으로는 원을 그리고 있기 때문에 Circular Linked List나 다른 방법이 더 쉬운 방법이었지만 이걸로 풀긴 했다.

 

02. Queue

 Queue를 생성해서 K - 1번째까지는 다시 Queue에 넣어주고 K번째 사람만 뽑아내면 되는 방법. 

 

---

풀이

 

Java

풀이 1 : LinkedList

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int N = info[0];
        int K = info[1];

        List<Integer> josephus = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        boolean[] visited = new boolean[N + 1];

        for (int i = 1; i < N + 1; i++) {
            josephus.add(i);
        }

        int idx = -1;

        while (result.size() < N) {
            int count = 0;

            while (count < K) {
                idx = (idx + 1) % N;
                if (!visited[idx]) {
                    count++;
                }
            }

            result.add(josephus.get(idx));
            visited[idx] = true;
        }

        StringBuilder sb = new StringBuilder();
        sb.append("<");
        for (int i = 0; i < result.size(); i++) {
            sb.append(result.get(i));
            if (i != result.size() - 1) {
                sb.append(", ");
            }
        }
        sb.append(">");
        System.out.println(sb);

    }
}

 

 LinkedList인 josephus, 결과를 담을 ArrayList result, 방문 여부를 확인한 boolean[] visited를 만들었다. 이제 josephus 리스트에 1부터 N까지의 수를 add하고 while문을 통해 result에 N개만큼의 결과가 채워질 때까지 반복한다. idx를 0이 아닌 -1부터 시작해서 K만큼 이동했을 때 'K'번째 사람을 가리킬 수 있도록 했다. 이 방법은 결과적으로 메모리 낭비가 심해 다른 방법이 좋을 수 있다.

 

풀이2 : Queue

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int N = info[0];
        int K = info[1];

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            queue.add(i);
        }

        StringBuilder sb = new StringBuilder();
        sb.append("<");

        while (!queue.isEmpty()) {
            for (int i = 0; i < K - 1; i++) {
                queue.add(queue.poll());
            }
            sb.append(queue.poll());
            if (!queue.isEmpty()) {
                sb.append(", ");
            }
        }

        sb.append(">");
        System.out.println(sb);
    }
}

 

 다음과 같이 일반적인 List가 아니라 Queue타입 변수와 함께 LinkedList를 생성해주었다. 이러한 방법이 가능한 이유는 자바의 LinkedList 클래스는 Deque 인터페이스를 구현하고, Deque 인터페이스가 Queue 인터페이스를 확장하기 때문이다.

 

 다음과 같이 queue에 1부터 N가지의 수를 add해준 뒤, while문에서 queue가 빌 때까지 블록 안의 내용을 실행시킨다. for문을 사용해 K - 1번까지는 queue에 앞에서 뺀 요소를 다시 뒤에 넣어준다. 그리고 나서 K번째 요소를 StringBuilder에 담는 식으로 진행된다.

 

Python

 

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().rstrip().split())

queue = deque()

for i in range(1, N + 1):
    queue.append(i)

print("<", end="")

while len(queue) > 0:
    for i in range(K - 1):
        queue.append(queue.popleft())

    element = queue.popleft()

    if (len(queue) > 0):
        print(element, end=", ")
    else:
        print(element, end="")

print(">")

 

 

 파이썬은 collections 모듈에서 deque를 지원하므로 아주 간단하게 구현할 수 있다.

 

 

Javascript (Nodejs)

 

const fs = require("fs");
const input = fs.readFileSync("input.txt").toString().trim().split(/\r?\n/);

let currentLine = 0;
function readLine() {
  return input[currentLine++];
}

const [N, K] = readLine().split(" ").map(Number);

let queue = [];

for (let i = 1; i < N + 1; i++) {
  queue.push(i);
}

let result = [];

while (queue.length > 0) {
  for (let i = 0; i < K - 1; i++) {
    queue.push(queue.shift());
  }
  result.push(queue.shift());
}

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

 

 

 Nodejs같은 경우에도 간단하게 처리할 수 있다. 자바스크립의 배열은 shift라는 메서드를 제공한다. shift 메서드는 배열의 가장 앞의 요소를 제거하고 반환하는 메서드이므로 deque와 유사하다. 마찬가지 방법으로 처리해준 뒤 console.log를 통해 출력해주면 되는데, 자바스크립트의 `(백틱)을 사용한 템플릿 리터럴을 사용하면 위의 다른 언어들보다 더 쉽게 문자열을 처리할 수 있다. ``안에 ${}구문을 사용해 result를 ", "를 기준으로 결합하는 result.join(", ") 표현식을 사용했다.