[백준] 요세푸스 문제 (큐, Queue, BufferReader, 1158번, Java)

qj

 

문제설명

입력 & 출력

 

나의 풀이

 

이번 문제는 요세푸스 순열에 대한 문제입니다.

 

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

 

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

 

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

1번째 사람부터 제거를 하면 3 ➡️ 6 ➡️  1 ➡️ 5 ➡️ 2 ➡️7➡️4 ➡️ 8 순서로 제거가 됩니다.

 

 

• 초기 상태
  • 1, 2, 3, 4, 5, 6, 7, 8
• 첫 번째 제거
  • 1, 2, 3, 4, 5, 6, 7, 8 (3 제거)
• 두 번째 제거
  • 4, 5, 6, 7, 8, 1, 2 (6 제거)
• 세 번째 제거
  • 7, 8, 1, 2, 4, 5 (1 제거)
• 네 번째 제거
  • 2, 4, 5, 7, 8 (5 제거)
• 다섯 번째 제거
  • 7, 8, 2, 4 (2 제거)
• 여섯 번째 제거
  • 4, 7, 8 (7 제거)
• 일곱 번째 제거
  • 8, 4 (4 제거)
• 마지막으로 남은 사람
  • 8

 

---

위와 같이 제거가 됩니다. 따라서 위 제거 과정을 기준으로 코드를 작성하면 됩니다.

 

먼저 빠른 입력을 위해서 Buffer를 사용하여 입력 N과K를 받아주고, 최종 반환을 위해 StringBuilder를 사용했습니다.

 

1부터 N까지 큐에넣어 큐를 초기화 합니다. 그리고 앞서 말한 제거 과정을 작성해야합니다.

 

요세푸스 규칙에 따라서 큐에 요소 즉 사람이 1명 남을 때 까지 반복하는 while문을 작성합니다.

 

그 다음 31번째 줄에서 K번째의 사람을 제거하기 위해서 K-1 까지 반복하는 반복문을 사용하여 K번째 앞까지 제거하여 큐의 뒤에 삽입합니다. 이는 poll() 메서드가 큐의 맨 앞 요소를 제거하는 특성을 활용한 것입니다.

 

그리고 최종적으로 반환할 StringBuilder에 append()메서드를 사용하여 K번째 요소를 계속해서 추가를 해줍니다.

 

그러면 최종적으로 sb에는 K번째로 제거된 사람이 존재하게 됩니다.

 

참고❗️

[JAVA] 입출력, BufferedReader, StringTokenizer, StringBuilder 알아보기

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