백준 1158: 요세푸스 문제 (JAVA) <Queue 활용>

문제 해석

 

원형 테이블 형식으로 1번부터 N번까지의 사람이 앉아있고 순서대로 K번째 사람을 제거한다.

이 과정은 모든 사람을 제거할 때까지 반복된다. 

N이 5, K가 3일 경우 

3 -> 1 ->  5 -> 2 -> 4 순으로 제거되는 순열이다.

 

알고리즘

 

Queue 를 이용하여 K번째 사람보다 앞에 있는 사람들을 뒤쪽으로 보내고 K번째 사람을 제거하는 방식을 적용하면 

원형 구조를 구현하면서 매번 K번째 사람을 제거할 수 있다.

 

Queue.

 

Queue 는 FIFO(선입선출) 구조를 가지고 있다. 입구와 출구가 다른 양쪽이 뚫려있는 구조이기에 입구에서는 데이터 삽입, 출구에서는 데이터 추출만 이루어진다. 이런 구조로 인해 추출 후 재삽입시 원형 구조를 구현할 수 있게 된다.

 

코드

 

 

문제에서 요구하는 출력형식을 구현하기 위해 StrungBuilder를 활용하여 문자를 계속 추가할 수 있게 하였고

비어있는 Queue에 1부터 N까지의 사람을 삽입하였다.

 

K번째 사람보다 앞에 있는 사람들은 poll(추출)하고 offer(삽입)하여 다시 뒤쪽으로 보내고

앞에 있는 사람들을 뒤쪽으로 보낸 후에는 K번째 사람을 poll(추출)하고 StringBuilder 객체에 추가해준다.

이 과정을 반복하여 K번째 사람을 계속해서 출력해낸다.

 

여기서 전체 인원 수가 K보다 작아지면 위의 for문이 의미가 없어지지만 while문 조건을 변경하여

전체 인원 수가 K보다 작을 때 따로 poll(추출)을 진행하더라도 반복문과 조건문을 사용해야 하기에

이를 최소화하고자 전체 인원 수가 1일 때만 분리하였다.