1158. 요세푸스 문제

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

---

문제

 

요세푸스 문제

요세푸스 순열을 구현해라!

문제의 요점을 살펴보면, 

입력받은 첫번쨰 값 N 명의 사람이 1부터 N 까지 차례대로 원을 이루어 앉아있다. 

이후 입력 받은 두번째 값 K 번쨰 사람이 사라지게 된다. 해당 과정은 N 명의 사람이 모두 제거될 때까지 계속된다. 

원에서 사람이 제거되는 순서를 (N,K) 라고 한다.

 

예제 입출력 

예제 입출력

예시로 제시된 입력문을 살펴보면,

입력 값 7 과 3은 "7명의 사람이 원을 둘러 앉아있고, 3번째 사람이 제거 된다." 라고 이해할 수 있다.

 

예제 입력문에 대한 출력 값을 살펴보면, 

출력 과정에 관한 요약도

위와 같은 과정을 거친 것을 확인할 수 있다.

 

출력 과정에 대해 살펴보면, 

 

배열의 각 원소들은 1 부터 N 번까지 차례대로 가진다. N 값은 1 부터 시작하기 때문에, 해당 배열의 인덱스 값은 N + 1 번까지 있을 것이다.

최초에 K 번째 요소가 삭제되게 되면 삭제된 값의 바로 다음 값부터 다시 삭제할 값을 카운트 한다. 해당 과정을 N 만큼의 크기를 가진 배열이 전부 없어질 때까지 실행하게 된다.

 

과정 자체는 굉장히 간단한데, 어떻게 구현할지에 대해 생각해볼 필요가 있었다.

 

Main

사용 알고리즘

자료구조와 큐

큐에 대한 설명

 

먼저 '큐' 라는 자료구조는 '스택' 과는 반대되는 자료구조이다. 

먼저 들어간 값이 가장 먼저 나오는 형태를 띄고 있는데, 큐에도 여러가지 종류가 있었다.

참고한 자료는 아래에 링크를 걸어두겠다.

 

 

우선 문제에 제시된 입력값들을 받아보겠다.

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // N 명의 사람
        int K = sc.nextInt(); // K 번째 사람이 삭제

 

이후 N 만큼의 크기를 가지는 배열을 생성해야하는데, 각 배열의 원소들은 1~N까지 이다.

일반적인 상황이라면 arr[] 배열 을 사용했겠지만, 이번 문제에서는 Queue 를 이용할 것이기 때문에 Queue 객체를 생성해, 1~N 까지의 값을 삽입해보겠다.

 

        Queue<Integer> q = new LinkedList<>(); // 큐 생성

        // 위에서 생성된 큐에 1~N까지의 값 삽입
        for (int i = 1; i <= N; i++) {
            q.offer(i); //offer 는 큐에 값을 입력하는 메서드이다.
        }

 

이제 생성한 q 안에 값이 1개만 남을 때까지 K 번째 값을 빼는 반복문을 만들어야한다. 

 

    while(!q.isEmpty()){ // q 안에 값이 없을 때까지 실행
            for(int i = 0; i<K; i++){
                if(i == K-1) // 만약 i 가 K -1 이랑 같다면 ex> K = 3, i = 3 -> 결과들을 누적할 ArrayList 에 q 의 헤드 값을 추가한다.
                    result.add(q.poll());
                else{ 
                    q.offer(q.poll()); 
                }
            }
        }

 

이후 간단한 형식을 갖춘 결과값을 출력해주면 문제를 해결할 수 있다.

 

System.out.print(" < ");

for (int i=0; i<N-1; i++){ //삭제된 값 출력문
       System.out.print(result.remove(0) + " , ");
}

System.out.print(result.remove(0) + " > ");

 

아래는 전체코드이다.

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Josephus {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = (Integer)sc.nextInt(); // N 명의 사람
        int K = (Integer)sc.nextInt(); // K 번째 사람이 삭제

        Queue<Integer> q = new LinkedList<>(); // 큐 생성
        List<Integer> result = new ArrayList<>(); // 나중에 결과를 보여줄 ArrayList

        // 위에서 생성된 큐에 1~N까지의 값 삽입
        for (int i = 1; i <= N; i++) {
            q.offer(i); //offer 는 큐에 값을 입력하는 메서드이다.
        }
        
        while(!q.isEmpty()){ // q 안에 값이 없을 때까지 실행
            for(int i = 0; i<K; i++){
                if(i == K-1) // 만약 i 가 K -1 이랑 같다면 ex> K = 3, i = 3 -> 결과들을 누적할 ArrayList 에 q 의 헤드 값을 추가한다.
                    result.add(q.poll());
                else{ 
                    q.offer(q.poll()); 
                }
            }
        }

        System.out.print(" < ");

        for (int i=0; i<N-1; i++){ //삭제된 값 출력문
            System.out.print(result.remove(0) + " , ");
        }

        System.out.print(result.remove(0) + " > ");
    }

}

 

 

 

참고사이트

큐 관련 설명: https://kwin0825.tistory.com/54

[자료구조] 큐(Queue)