[백준] 1158 요세푸스 문제 - Java

문제 - 요세푸스 문제

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

 

 

문제 설명 

 

입력

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

 

출력

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

 

 

예제 입력

7 3

 

예제 출력

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

---

 

접근 방법

 

- 문제를 보면 숫자를 차례대로 탐색하고 K 번째 숫자를 제거하고 그런식으로 처리를 한다 

- 여기에서 생각 해볼 자료구조가 링크드리스트나 큐를 생각했다

- 큐를 생각한 이유는 차례대로 탐색을 하면서 K번째 이전의 값들은 다시 빼고 다시 넣는 형태가 맞는 것 같아서 생각을 했다 그리고 숫자를 차례대로 탐색하는 형식이라 선입선출 형식과 맞는 것 같다

 

---

코드 작성

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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

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

            for (int i = 1; i <= N; i++) {
                queue.offer(i);
            }

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

            while (queue.size() != 1) {
                for (int i = 0; i < K - 1; i++) {
                    queue.offer(queue.poll());
                }
                sb.append(queue.poll()).append(", ");
            }
            sb.append(queue.poll()).append(">");
            System.out.println(sb);
        }
    }
}

 

---

문제 풀고 느낀점

 

- 이 문제는 자료구조만 잘 선택해서 데이터 처리를 어떻게 하는냐는 문제이다

- 어렵지 않은 문제이지만 적절한 자료구조를 선택하지 않으면 로직이 난해 해질수도 있을 것 같다