백준 자바 1158번 요세푸스

이 문제는 코드를 짜는 시간보다 어떻게 코드를 작성해야할지 알고리즘을 고민한 시간이 더 길었던 것 같다. 

선입선출인 큐를 이용하였다.

 

package boj_basic.cp_1;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Q1158요세푸스문제 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String[] arr = br.readLine().split(" "); // 7이랑 3을 나눠 배열에 담고,
        int N = Integer.parseInt(arr[0]); // N = 0번째 인덱스에 있는 7
        
        int K = Integer.parseInt(arr[1]); // K = 1번째 인덱스에 있는 3
        int num = K; 
        
        Queue<Integer> queue = new LinkedList<>();
        
        for(int i = 1; i<=N; i++) {
        	queue.add(i); //큐에 1234567 넣음
        }
        
        bw.write("<");
   
        while(queue.size()!=1) {
        	for(int i = 1; i<num; i++) { //3번째꺼 전까지, 즉 첫번째와 두번째를
        		queue.add(queue.remove());  //1,2를 큐에서 빼서 다시 큐에 집어넣음 3456712 이 상태.
        	}
        	bw.write(queue.remove()+", ");	//3을 큐에서 삭제. 456712 이 상태. 
        	//1234567 -> 3!456712 -> 456712 -> 6!71245 -> 71245 -> 2!4571 -> 4571 -> 7!145 -> 145 -> 5!14 -> 14 -> 1!4 -> 4 
        }
        
        bw.write(queue.remove()+""); //큐에 하나 남았을 때는 그냥 빼서 출력 4!
        
        bw.write(">");
        
        bw.flush();
        bw.close();
        br.close();
        

	}

}

주석을 자세하게 적었다. 확실히 코딩할 때 주석을 적는 게 코딩을 하면서 더 정리가 되는 것 같고, 나중에 볼 때도 이해하기 쉬운 거 같다! 되게 가시적이라서 잘 짠 것 같다는 칭찬도 들었다.ㅎㅎ

 

사실 나머지(%)를 이용하여 풀고 싶었는데, 잘 안됐다. 나머지 식을 이용한 풀이가 있는지 찾아봐야겠다.

나와 다른 방법으로 푼 사람들의 풀이도 궁금해지는 문제이다.