[JAVA] 백준 (실버4) 1158번 요세푸스 문제

링크

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

---

문제 설명

(정답률 48.613%)
요세푸스 문제는 다음과 같다.

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

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

---

입력 예제

7 3

---

출력 예제

<3, 6, 2, 7, 5, 1, 4>

---

나의 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int idx = k - 1;  //k번째의 인덱스

        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> answer = new ArrayList<>();

		//1부터 n까지의 정수를 순서대로 list에 추가
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }

		//문제 조건에 맞게 list에서 하나씩 뽑아내어 answer에 추가
        for (int i = 0; i < n; i++) {
        	//k번째 원소를 answer에 추가
            //인덱스가 list의 크기보다 클 경우 k번째 인덱스를 구하기 위해 나머지 연산 사용     
            answer.add(list.get((idx) % list.size()));
            idx %= list.size();
            //answer에 추가한 원소를 list에서 제거
            list.remove(answer.get(i));
            //다시 k번째 원소를 제거하기 위해 인덱스를 k만큼 증가
            idx += k - 1;
        }

        String result = answer.toString().replace("[", "<");
        bw.write(result.replace("]", ">"));
        bw.close();
    }
}

list = [1, 2, 3, 4, 5, 6 7]
idx = 2 % 7 = 2
list = [1, 2, 4, 5, 6, 7]
idx = 4 % 6 = 4
list = [1, 2, 4, 5, 7]
idx = 6 % 5 = 1
list = [1, 4, 5, 7]
idx = 3 % 4 = 3
list = [1, 4, 5]
idx = 5 % 3 = 2
list = [1, 4]
idx = 4 % 2 = 0
list = [4]
idx = 0 % 1 = 0

---

다른 사람의 풀이

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
 
        Queue<Integer> queue = new LinkedList<>();
 
        //1번부터 N번까지 N명의 사람
        for (int i = 1; i <= n; i++) {
            queue.offer(i);
        }
 
        StringBuilder sb = new StringBuilder();
        sb.append("<");
        //queue의 크기가 1이 될때까지 반복
        while (queue.size() != 1) {
        	//k - 1번째 까지 원소들을 뒤로 보낸다
            for (int i = 0; i < k - 1; i++) {
                queue.offer(queue.poll());
            }
            //queue 맨 앞에 있는 값이 k번째 원소가 된다
            sb.append(queue.poll()).append(", ");
        }
        
        sb.append(queue.poll()).append(">");
        System.out.println(sb);
    }
}

---

정리

문제를 읽고 수학적인 문제인거 같아 고민을 하다가
그냥 직관적으로 문제가 제시하는데로 k번째 숫자를 뽑아냈다.
줄어드는 list에 맞춰 인덱스값을 나머지 값으로 갱신해줬어야 했다.
하지만 문제의 의도는 큐를 이용한 풀이였다..
다른 사람의 풀이를 보니 너무 간단하게 풀린거 같았다.
k번째를 첫번째로 옮기고 그 전 값들은 그냥 뒤로 밀어넣는 것이였다.
Queue 메소드는 다음과 같다.

기능	Throws exception	Returns special value
삽입(Insert)	add(e)	offer(e)
삭제(Remove)	remove()	poll()
헤드 조회(Head Examine)	element()	peek()