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

27 Jun 2023 in Algorithm on Algorithm

screenshot

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

❓문제

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

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다.

K,N 범위 : 1 ≤ K ≤ N ≤ 1,000

🖊️풀이법

우선, 문제에 대해서 알아보자.
총 7번의 반복문이 실행되며, 플로우는 다음과 같다.

초기화 상태{1, 2, 3, 4, 5, 6, 7} -> {}

{1, 2, 4, 5, 6, 7} -> {3}
{1, 2, 4, 5, 7} -> {3, 6}
{1, 4, 5, 7} -> {3, 6, 2}
{1, 4, 5} -> {3, 6, 2, 7}
{1, 4} -> {3, 6, 2, 7, 5}
{4} -> {3, 6, 2, 7, 5, 1}
{} -> {3, 6, 2, 7, 5, 1, 4}

와 같이, K번째 순서의 숫자를 빼서 출력문에 더하면 된다.

이번 문제는 2가지 방법을 사용하여, 풀어보았다.

Queue 사용법

queue{1,2,3,4,5,6,7} result{}

첫번째

loop 1 : {1, 2, 3, 4, 5, 6, 7} → {2, 3, 4, 5, 6, 7, 1}
loop 2 : {2, 3, 4, 5, 6, 7, 1} → {3, 4, 5, 6, 7, 1, 2}
loop 3 : {3, 4, 5, 6, 7, 1, 2} → 3 출력

두번째

loop 1 : {4, 5, 6, 7, 1, 2} → {5, 6, 7, 1, 2, 4}
loop 2 : {5, 6, 7, 1, 2, 4} → {6, 7, 1, 2, 4, 5}
loop 3 : {6, 7, 1, 2, 4, 5} → 6 출력

세번째

loop 1 : {7, 1, 2, 4, 5} → {1, 2, 4, 5, 7}
loop 2 : {1, 2, 4, 5, 7} → {2, 4, 5, 7, 1}
loop 3 : {2, 4, 5, 7, 1} → 2 출력

네번째

loop 1 : {4, 5, 7, 1} → {5, 7, 1, 4}
loop 2 : {5, 7, 1, 4} → {7, 1, 4, 5}
loop 3 : {7, 1, 4, 5} → 7 출력

다섯번째

loop 1 : {1, 4, 5} → {4, 5, 1}
loop 2 : {4, 5, 1} → {5, 1, 4}
loop 3 : {5, 1, 4} → 5 출력

여섯번째

loop 1 : {1, 4} → {4, 1}
loop 2 : {4, 1} → {1, 4}
loop 3 : {1, 4} → 1 출력

일곱번째

loop 1 : {4} → {4}
loop 2 : {4} → {4}
loop 3 : {4} → 4 출력

위의 방식으로 K-1번 만큼 queue.poll 값을 임시로 담은 후 offer하고, K번 째 값을 poll한 후 출력문에 답으면 된다.

Queue 정답 코드

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        sb.append("<"); 
        Queue<Integer> queue = new LinkedList<>(); // 큐 선언
        for(int i = 1; i <= N; i++){ //큐에 1~N만큼 담기
            queue.offer(i);
        }
        while(queue.size() != 0){ //큐의 크기가 0이될때까지 반복
            for(int i = 0; i < K-1; i++){ // K-1번 만큼 반복
                int tmp = queue.poll(); //tmp에 queue.poll값을 담고, poll
                queue.offer(tmp); // 다시 tmp 를 queue에 offer
            }
            sb.append(queue.poll()).append(", "); //K번째 값을 sb에 담는 것과 동시에 poll
        }
        sb.setLength(sb.length()-2); //모든 반복문이 순회한 다음 마지막 요소에 ", "를 제거
        sb.append(">"); 
        System.out.println(sb); //정답 출력
    }
}

다음으로는 LinkedList를 이용하는 방법이다.
해당 문제는 데이터의 삽입과 제거가 잦은 문제이므로, ArrayList보다 LinkedList가 훨씬 효율적이라 판단하였다.

우선 LinkedList를 사용할 경우 플로우는 다음과 같다.
다음 플로우를 살피며, 삭제되는 값의 idx를 정리하고, 규칙을 도출 해낸 후 해당 규칙을 코드로 적용하면된다.

초기화 상태{1, 2, 3, 4, 5, 6, 7} -> {}

{1, 2, 4, 5, 6, 7} -> {3} -> 3의 idx 는 2
{1, 2, 4, 5, 7} -> {3, 6} -> 6의 idx 는 4
{1, 4, 5, 7} -> {3, 6, 2} -> 2의 idx 는 1
{1, 4, 5} -> {3, 6, 2, 7} -> 7의 idx 는 3
{1, 4} -> {3, 6, 2, 7, 5} -> 5의 idx 는 2
{4} -> {3, 6, 2, 7, 5, 1} -> 1의 idx 는 0
{} -> {3, 6, 2, 7, 5, 1, 4} -> 4의 idx 는 0

처음 초기 idx = K - 1이다.
그렇다면, list에서 K - 1번째 값이 remove되기 때문에, 다음 idx 값은 idx + K - 1이 된다.
만약 idx 값이 size를 초과하는 경우의 idx값은 idx % 리스트의 사이즈가 된다.
따라서, idx = (idx + (K -1)) % list.size라는 규칙을 찾을 수 있다.

LinkedList 정답코드

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        sb.append("<");
        LinkedList<Integer> list = new LinkedList<>();
        for(int i = 1; i <= N; i++){
            list.add(i);
        }
        int idx = 0; //idx 초기화
        while(list.size() > 0){
            idx = (idx + (K - 1)) % list.size(); //삭제해야 하는 리스트이 idx값 할당
            sb.append(list.remove(idx)).append(", "); //list에서 삭제와 동시에 sb에 담기
        }
        sb.setLength(sb.length()-2);
        sb.append(">");
        System.out.println(sb);
    }
}

정리

두 가지 풀이의 성능 차이는 다음 사진과 같다. screenshot

Queue의 경우, 계속해서 큐에 원소들을 다시 넣는 작업을 반복하기 때문에, 보다 더 높은 메모리와 연산시간이 필요하다. 하지만 구현방법이 간단하고, 코드를 보다 이해하기 쉽다는 장점이 있다.
LinkedList의 경우, 바로바로 출력해야 하는 요소들을 담으며, 제거하기 때문에, 보다 낮은 메모리와 빠른 연산속도를 가지지만, 규칙에 대해서 생각해보아야 하며, 구현 방법이 Queue방식에 비해 다소, 까다롭다.(?)

두 풀이 방식을 바탕으로, 효율적인 알고리즘도 중요하지만, 협업 시에 서로의 코드를 보고 작업을 해야하는 경우도 있기 때문에, 반드시 코드의 가독성과 유지보수의 관점도 생각하면서, 코드를 작성하자.

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

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

❓문제

🖊️풀이법

Queue 정답 코드

LinkedList 정답코드

정리

개발하는 토마토🍅

Error

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

❓문제

🖊️풀이법

Queue 정답 코드

LinkedList 정답코드

정리

Templates (for web app):

Error