[백준, 11866번] 요세푸스 문제 0 (구현, 큐 Queue , Java)

문제설명

입력 & 출력

나의 풀이

이번 "백준 - 요세푸스 문제 0"문제는 주어진 수 N과 K에 대해, 1부터 N까지의 숫자에서 K번째마다 숫자를 제거하고 그 순서를 출력하는 문제입니다. 

[자료구조 JAVA] 선형 구조 큐(Queue) 클래스 알아보기 ✔

요세푸스 순열이란 문제에서 나와있듯이 "원형으로 앉아 있는 N명의 사람들이 순서대로 제거되는 과정 "입니다.

 

이 때 매번 K번째 사람을 제거하며, 마지막 한 사람이 남을 때까지 이 과정을 반복합니다.

 

이해를 돕기위해 위 그림을 기준으로 예로 들자면 8명의 사람이 위와 같이 원형으로 앉아 있습니다.

 

이 문제는 큐(Queue) 자료구조를 사용하여 쉽게 해결할 수 있습니다. 그 이유는 큐는 FIFO(First In, First Out) 특성을 가지므로 순서를 유지하며 제거하기에 적합합니다. 또한 K번째 사람을 제거한 후에는 다시 순서를 재정렬하여 이어지는 K번째 사람을 제거해야 하므로, 순환 구조를 구현하는 데 큐가 효율적입니다.

 

전체 코드

 

문제의 핵심은 K번째가 아니라면, 큐의 poll() 메서드를 사용하여 꺼낸 값을 다시 큐에 추가하는 것입니다. 이때, cnt 변수를 사용해 값을 증가시키며, cnt가 K에 도달하면 0으로 초기화하여 다음 순환을 준비합니다.

 

그리고 "," 쉼표가 마지막에 추가되기 때문에 setLength()메서드를 사용하여 길이를 조정하여 마지막 공백과 쉼표를 제거하여 출력해 마무리했습니다.