[백준알고리즘] 11866번: 조세퍼스 문제 0 -Java

[백준알고리즘] 11866번: 조세퍼스 문제 0 -Java

https://www.acmicpc.net/problem/11866

11866번: 조세퍼스 문제 0

 

큐, 덱에 있는 문제이고, 큐를 이용한 문제라고 나와있는데 굳이 큐를 사용해야 되나? 싶은 문제였다.

 

여기서 큐의 특징 FIFO가 나타날만한 부분은 일치하는 값을 차례대로 뽑아서 큐에 넣은 후에 마지막에 한 번에 쭉 출력해 내는 것이다.

 

 

굳이 사용하고자 한다면, 둥글게 앉은 다음에 예에서 3번째 사람마다 빠진다고 했을 때를 예를 들어보면 다음과 같이 이용이 가능하다.

 

앉아있는 상태	제외된 상태
<1, 2, 3, 4, 5, 6, 7>	<>
<2, 3, 4, 5, 6, 7, 1>	<>
<3, 4, 5, 6, 7, 1, 2>	<>
<4, 5, 6, 7, 1, 2>	<3>
<5, 6, 7, 1, 2, 4>	<3>
<6, 7, 1, 2, 4, 5>	<3>
<7, 1, 2, 4, 5>	<3, 6>
...	...

 

poll 해준 것을 다시 추가해주는 방법이다. 조건이 맞을 때에만 따로 빼주게 하면 된다.

 

 

하지만 굳이 뺐다가 다시 넣는 과정을 해야할 필요를 못 느꼈다. 그래서 그냥 인덱싱을 해주기로 했다. 실제로 인덱싱이 더 빠를 것이라 생각이 드는데 정확한 비교는 안 해봤다.

 

여기서는 인덱싱을 해주기 위해서 제외된 인덱스인지 확인하기 위해서 check배열을 ArrayList로 하나 만들어주었다.

제외된 값이라면 그냥 넘겨주었고, 제외가 안된 값이라면 카운트도 세주었다. 

 

카운트는 여기서는 K를 의미한다. K번째마다 뽑아내야 하기 때문에 별도로 카운팅을 해주었고, total은 현재 제외된 값의 수이다.

 

idx도 범위를 넘기지 않기 위해서 그냥 증가를 시켜주는 것이 아니라 초기화도 해주면서 진행했다.

idx++;
idx %= N;

을 해주었어도 됐을 것 같다.

 

 

아무튼 어려운 문제는 아니었으나 깔끔하다고 생각됐던 코드는 밑에 참고 링크를 따로 걸어두겠다.

 

import java.io.*;
import java.util.ArrayList;
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(), " ");
		StringBuilder sb = new StringBuilder();
		sb.append("<");
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int i, idx = 1, cnt = 1, total = 0;
		
		ArrayList<Boolean> check = new ArrayList<Boolean>();
		for(i = 0; i < N; i++) {
			check.add(false);
		}
		
		while(total != N) {
			if(check.get(idx - 1)) {
				idx = idx == N ? 1 : idx+1;
				continue;
			}
			
			if(cnt == K) {
				check.set(idx - 1, true);
				total++;
				sb.append(idx);
				if(total != N) sb.append(", ");
				
				cnt = 1;
			}
			else {
				cnt++;
			}
			
			idx = idx == N ? 1 : idx+1;
		}
		
		sb.append(">");
		System.out.println(sb.toString());
	}

}

 

 

<참고>

https://hyeooona825.tistory.com/15

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다