📑 1. 문제설명
✅ 문제
이문제는 유대인 역사가 플라비우스 요세푸스가 만든 문제이다.
N명의 사람이 원 형태로 서 있다. 각 사람은 1부터 N까지 번호표를 갖고 있다. 그리고 임의의 숫자 K가 주어졌을 때 다음과 같이 사람을 없앤다.
- 1번 번호표를 가진 사람을 기준으로 K번째 사람을 없앤다.
- 없앤 사람 다음 사람을 기준으로 하고 다시 K번째 사람을 없앤다.
N과 K가 주어질 때 마지막에 살아 있는 사람의 번호를 반환하는 solution() 함수를 구현해주세요
✅ 제약조건
- N과 K는 1이상 1000이하의 자연수이다.
✅ 입출력 예
| N | K | return |
| 5 | 2 | 3 |
💡 2. 풀이 과정

입출력 예를 그대로 그림으로 구현하려고 한다.
- N = 5, K = 2 이고 사람마다 1~5번까지의 숫자를 붙여 원형으로 배치한다.
- 그리고 첫번째 코드가 실행될 때의 기준은 1번이다.
주어진 예시에서 k = 2인데, k=2 라는 건 현재 위치에서 바로 다음 사람을 제거한다는 뜻이다.
- k=2 일 때, 첫 번째 사람을 건너뛰고 두 번째 사람을 제거한다.
- 그 다음 차례는 제거된 사람의 다음 사람으로 기준이 넘어간다.
- 기준이 된 사람을 건너뛰고 옆 사람을 제거한다 (k = 2)
- 이 과정을 남은 사람이 한 명이 될 때까지 반복하면 된다.
즉, 매번 바로 옆에 있는 사람을 제거하는 것이기때문에 원 형태로 배열된 사람들이 한 칸씩 건너면서 사라지는 패턴을 가지게 된다.

기준이 1번이기 때문에 K번째 사람은 2번 번호표를 가진 사람이다. 이 사람을 첫번째로 제거하고, 다음 위치를 3번으로 이동한다.

기준이 3번이므로 3에서시작해서 2번째 사람인 4번을 제거한다. 그리고 새로운 기준은 5번이 된다.

5번을 기준으로 k = 2번째 사람인 1번을 제거하고 새로운 기준은 3번으로 넘어온다.

3번이 기준이므로 그 다음 사람인 5번을 제거한다.

가장 마지막으로 제거되는 사람은 3번이다.
⭐ 3. 정답코드
package algo03.StackAndQueue;
import java.util.LinkedList;
import java.util.Queue;
public class queue_josephus {
public static void main(String[] args) {
System.out.println(solution(5, 2)); // 결과: 3
}
/**
* 요세푸스 문제를 해결하는 함수
*
* @param N 사람의 수 (1부터 N까지 번호가 있음)
* @param K 제거할 순번 (K번째 사람을 계속 제거함)
* @return 마지막에 살아남은 사람의 번호
*/
public static int solution(int N, int K) {
// 큐(Queue) 생성: 원형 구조를 시뮬레이션하기 위해 사용
Queue<Integer> queue = new LinkedList<>();
// 1부터 N까지의 사람을 큐에 추가
for (int i = 1; i <= N; i++) {
queue.add(i);
}
// 마지막 한 명이 남을 때까지 반복
while (queue.size() > 1) {
// K번째 사람을 제거하기 위해 K-1번 앞의 사람을 뒤로 보냄
for (int i = 1; i < K; i++) {
queue.add(queue.poll()); // 맨 앞 사람을 빼서 큐의 뒤에 추가
}
queue.poll(); // K번째 사람 제거
}
// 마지막 남은 사람 반환
return queue.poll();
}
}
큐(Queue) 는 간단하게 말해서 FIFO (First In, First Out) 구조를 가진 자료 구조로 먼저 들어온 데이터가 먼저 나가는 방식이다. Java에서 LinkedList를 사용해 Queue를 구현 할 수 있다.
- poll() → 맨 앞 원소를 제거하고 반환하기
- add() → 큐의 뒤에 새로운 원소 추가하기
먼저 큐를 초기화하고, 1 ~ N까지 사람을 큐에 삽입한다. 그리고 나서 K번째 사람을 제거하는 과정은 아래와 같다.
- queue.add(queue.poll()); → K-1번 동안 맨 앞 사람을 빼서 뒤로 이동한다.
- queue.poll(); → K번째 사람을 제거한다.
- return queue.poll(); → 마지막 한 명이 남으면 반환한다.
🐦 4. 같은 유형 문제
[프로그래머스] (Java) 카드뭉치 (큐)
📑 1. 문제설명 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr💡 2. 풀이 과정이 문제는 queue 로 푸는 문제이다 (이걸
awesomepossum.tistory.com
[프로그래머스] (Java) 주식가격 (스택/큐)
📑 1. 문제설명💡 2. 접근방식이중for문현재 인덱스에 있는 요소과 이후 모든 값을 비교하면서 현재 요소가 비교하고 있는 요소보다 커지면 break;를 걸어준다.그 전까지는 answer[i]++을 해 준다.
awesomepossum.tistory.com
[프로그래머스] (Java) 다리를 지나는 트럭 (스택/큐)
📑 1. 문제설명💡 2. 접근방식 Queue트럭 진입 로직: 다리의 맨 앞 트럭이 나가고 새로운 트럭이 다리에 올라갈 수 있는지 확인한 후 다리에 추가이동시간: 트럭이 다리 위에 오르면 매 1초마다
awesomepossum.tistory.com
[프로그래머스] (Java) 프로세스 문제풀이 (스택/큐)
1. 문제설명 예제 #1문제에 나온 예와 같습니다. 예제 #26개의 프로세스 [A, B, C, D, E, F]가 대기 큐에 있고 중요도가 [1, 1, 9, 1, 1, 1] 이므로 [C, D, E, F, A, B] 순으로 실행됩니다. 따라서 A는 5번째로 실
awesomepossum.tistory.com
[프로그래머스] (Java) 기능개발 (스택/큐)
1. 문제설명프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이
awesomepossum.tistory.com
'코딩테스트 > JAVA테스트' 카테고리의 다른 글
| [리트코드] LeetCode Longest Common Prefix (Easy) in Java (23) | 2025.02.22 |
|---|---|
| [프로그래머스] (Java) 카드뭉치 (큐) (6) | 2025.02.20 |
| [프로그래머스] (Java) 예상대진표 (트리) (13) | 2025.02.20 |
| [프로그래머스] (Java) 크레인 인형 뽑기 게임 (스택) (9) | 2025.02.18 |
| [코딩테스트] (Java) 십진수를 이진수로 변환하기 (스택) (17) | 2025.02.17 |