[백준 / BOJ] 1158번 : 요세푸스 문제 (JAVA)

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

1158번: 요세푸스 문제

자료구조 Queue

막상 Queue를 사용해야 한다는 것을 알게 되니 어이없을 만큼 쉽게 풀렸지만, 그 전에는 배열을 사용해 방문 체크를 할 생각을 해서 어렵게 느껴졌던 문제다. 배열로 방문 체크를 한다면 최대 5,000명인 인원수를 다 찾아봐야 할 수도 있으니까.

 

인원수 N이 5000이고, M 또한 5000이라면 5000명을 다 지우기 위해 5000 ** 2 = 25000000번의 연산이 필요했을 것이다. 물론 그래도 시간 초과가 나진 않았겠지만 너무 비효율적으로 느껴졌다. 또 배열로 진행하면, N에서 다음으로 넘어갈 때 if문으로 1로 바꿔줄 필요도 있다.

 

Queue를 사용하면 위와 같은 문제가 해결된다. 방문한 사람들은 queue에서 아예 빠져버리기 때문에, 다음번 검색할 때의 N수가 작아진다. 또 queue에 넣어놓은 게 정해진 순서이니, N을 초과한 경우에는 어떻게 하느니 하는 고민을 할 필요가 없었다.

 

문제를 보고 어떤 자료구조를 사용하는 게 편리할지 빠르게 결정할 수 있게 노력해야 겠다.

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());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		Queue<Integer> que = new LinkedList<>();
		
		for (int i = 1; i <= N; i++) {
			que.offer(i);
		}
		StringBuilder sb = new StringBuilder();
		sb.append("<");
		while(!que.isEmpty()) {
			for (int i = 0; i < M - 1; i++) {
				que.offer(que.poll());
			}
			sb.append(que.poll()).append(", ");
		}
		
		sb.delete(sb.length() - 2, sb.length());
		sb.append(">");
		
		System.out.println(sb);
		
		
	}

}