백준 1158 요세푸스 자바[java]

• 요세퍼스 문제

1158번: 요세푸스 문제

 

 

(N K) 두 수가 주어진다.

N명의 사람이 원탁에 둘러앉아 있고,

K번째 사람을 제거해 나갈때

제거한 사람을 순서대로 출력하는 문제이다.

 

처음엔 LinkedList 인덱스 번호로 접근했다.

근데 이렇게 하면 제거된 사람들까지 같이 고려하게 된다.

 

어떻게 하면 남아있는 사람들만 고려할 수 있을까 고민했고,

iterator가 떠올랐다.

하지만 iterator를 사용하게 되면 마지막 값에 도달했을때

처음부분으로 다시 돌아오는 부분을 구현할 수 없었다.

조금 더 고민하다가 다른 분의 풀이를 봤다.

 

 

원탁에 둘러앉았기 때문에 계속 돌면서 

판단하고 제거하고 해야한다.

이를 Queue의 특성을 이용하여 구현했다.

 

맨 앞에 있는 값(가장 먼저 들어간 값)을 빼와서 K번째 값인지 판단한다.

K번 반복되어 나온 값이 아니라면 다시 큐에 넣어준다.

K번 반복되어 나온 값이라면 제거해주며 양식에 맞게 출력한다.

 

예를들어

 7  3을 입력했을때 (N=7 K=3) 과정을

그림으로 표현하면 아래와 같다.

 

큐에 1~7이 순서대로 들어가고,

맨 앞에 있는 값인 1이 나와서 판단과정을 거친다.

K=3이기때문에 3번째 나온 값을 제거해줘야한다.

1은 첫번째 나온 값이기때문에 큐에 다시 들어간다.

 

 

 

 

 

 

2역시 동일한 과정을 거친다.

 

 

 

 

3이 나오고,

3번째 나온 값이기 때문에

remove()메서드로 제거해준다.

remove()메서드는 제거해주면서 그 값을 반환하기에

이를 이용하여 출력양식에 맞게 그 값을 출력한다.

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        LinkedList<Integer> lik = new LinkedList<>();
 
        String[] arr = br.readLine().split(" ");
        int N = Integer.parseInt(arr[0]);
        int K = Integer.parseInt(arr[1]);
 
        for(int i = 1; i < N+1; i++){
            lik.add(i);
        }
        bw.write("<");
 
        while(!lik.isEmpty()){
            for(int i =0; i < K; i++){
 
                if(i == K-1 && lik.size() > 1) { //K번째에 나온 값인지 && ","를 붙여야 하는지 판단
                    bw.write(lik.remove()+", ");
                }else if(i == K-1) { //마지막에 나오는 값은 "," 없이 ">"붙여서 나오게끔 
                    bw.write(lik.remove()+">");
                }else { //K번째에 나오는 값이 아니라면 제거하면서 다시 
                    lik.add(lik.remove());
                }
            }
        }
        br.close();
        bw.flush();
        bw.close();
    }
}