알고리즘 문제 풀이를 블로그에 올리는 이유는 풀이, 코드를 기록하기 위함이니
앞으로 문제를 다 긁어오기보다 링크만 두고 풀이가 잘 보이도록 포스팅 할 예정입니다!

📄 문제

[백준] 요세푸스 문제

---

👩‍💻 풀이

1. 문제 이해

이 문제는 N명의 사람이 원을 이루며 둘러 앉아 있을 때
남은 사람이 없을 때까지 순서대로 K번째 사람을 제거하면서 제거되는 사람의 번호(순서)를 구하는 문제이다.

입출력 예로 제시된 7, 3을 보자

1,2,3,4,5,6,7
1,2,_,4,5,6,7	=> 3
1,2,_,4,5,_,7	=> 6
1_,_,4,5,_,7	=> 2
1,_,_,4,5,_,_	=> 7
1,_,_,4,_,_,_	=> 5
_,_,_,4,_,_,_	=> 1
_,_,_,_,_,_,_	=> 4

때문에 출력값은 <3, 6, 2, 7, 5, 1, 4>이 된다.

2. 이중 반복문 활용 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
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());

        LinkedList<Integer> numbers = new LinkedList<Integer>();
        for(int i = 0; i < n; i++) {
            numbers.add(i+1);
        }

        System.out.println(josephus(numbers, k));
    }

    static String josephus(LinkedList list, int x) {
        String str = "<";
        while(!list.isEmpty()) {
            for (int i = 0; i < x; i++) {
                if (i == x - 1) {
                    int temp = (Integer)list.remove();
                    if (list.size() == 0) {
                        str += temp;
                    } else {
                        str += temp + ", ";
                    }
                } else {
                    list.add(list.remove());
                }
            }
        }
        return str + ">";
    }
}

코드에서 연결 리스트 자료구조를 사용하기는 했지만,
연결 리스트와 노드를 구현하여 해당 자료구조만의 특징을 십분 활용하지 못한 것이 아쉽다.
원형 연결 리스트를 잘 구현한다면, k만큼 next하여 remove하는 방식으로 풀이가 가능할 듯 하다! (도전🔥)