LinkedList/Queue의 활용 - BOJ 1158 요세푸스 문제

문제

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

1158번: 요세푸스 문제

 

 

문제 접근

• 원형으로 돌아가 K만큼 떨어진 사람을 계속해서 빼내어 모든 인원이 빠질 때 까지 반복한다. 이때 빼낸 사람들을 순차적으로 출력한 것이 요세푸스 순열이다.
• 해당 문제는 Queue 문제이지만, LinkedList로도 풀 수 있는 문제이다. 애초에 Java에서 Queue의 구현체로 LinkedList를 사용했으니 사용하는 메서드만 다르지 동작을 동일하게 할 수 있다.

 

 

답안 코드

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

public class Solution2 {
    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());

        LinkedList<Integer> list = new LinkedList<>();

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

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

        while(!list.isEmpty()){
            for(int i = 0; i < K - 1; i++){
                list.addLast(list.pollFirst());
            }

            sb.append(list.pollFirst());
            if (!list.isEmpty()){
                sb.append(", ");
            } else{
                sb.append(">");
            }
        }

        System.out.println(sb.toString());
    }
}

• 보면 알겠지만 Queue로 구현할 경우 list.addLast(list.pollFirst())가 queue.offer(queue.poll()) 등으로 수정되면 나머지는 모두 동일하다.