[ Backjoon - 1158번 ] 요스푸스 문제 ( java )
1158번: 요세푸스 문제
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
www.acmicpc.net
📚 Table of Contents
문제
입력
출력
예제
문제 풀이
문제 접근 ( 알고리즘 )
- 입력 :
- N : N명의 사람의 수
- K : K번째 사람을 뽑아 요세푸스 순열을 만든다.
- N명이 사람이 다 뽑힐 때 까지 반복
예제 1번
입력 : 7 31 2 3 4 5 6 7 의 사람이 있다.
3번째 사람을 뽑아 출력 시킨다.1 2 4 5 6 7
<3>1 2 4 5 7
<3 6>1 4 5 7
<3 6 2>1 4 5
<3 6 2 7>1 4
<3 6 2 7 5>4
<3 6 2 7 5 1><3 6 2 7 5 1 4>
풀이
ArrayList 사용
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Backjoon_1158 {
public static void main(String[] args) throws IOException {
// 입력을 받기 위해 사용
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
//입력 변수 선언
int N, K;
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
// 출력을 위해 사용
StringBuilder sb = new StringBuilder();
sb.append("<");
// 문제 풀이
// N명의 사람을 넣을 배열 선언
ArrayList<Integer> list = new ArrayList<>();
// N만큼 반복, 배열에 넣는다.
for (int i = 1; i <= N; i++) {
list.add(i);
}
// K번째 사람을 찾기위한 변수
// -1인 이유, K번째 사람의 인덱스가 K-1 이기 때문이다.
int idx = -1;
// 배열이 빌 때까지 반복
while (!list.isEmpty()) {
// K만큼 반복
for (int i = 0; i < K; i++) {
// idx 증가 K 만큼
idx ++;
// System.out.println("idx = " + idx);
// idx가 배열의 크기보다 크거나 같은 경우
if (idx >= list.toArray().length) {
// 다시 0으로
idx = 0;
// System.out.println("idx 0으로");
}
}
// System.out.println(list);
// k번째 사람을 출력 시킨다.
sb.append(list.get(idx)).append(", ");
// System.out.println("출력 idx = " + idx); // 후 배열에서 제거
// --를 하는 이유, 배열을 제거하면 현재 idx가 다음 요소를 가르키기 때문이다.
list.remove(idx--);
// System.out.println("idx = " + idx);
}
sb.append(">");
System.out.print(sb.toString());
}
}
idx를 이용하여 요소를 찾는 과정에서 시간을 초과한 것 같다.
Queue 사용
큐를 사용하여 문제를 해결 했다.
예제 1번
입력 : 7 31 2 3 4 5 6 7 의 사람이 있다.
3번째 사람을 뽑아 출력 시킨다.K - 1 만큼 q.poll( ), q.offer( ) 하여
3번째 사람이 맨 앞으로 오도록 만든다.1 2 3 4 5 6 7 / q.poll( ) => 1 / q.offer( 1 )
2 3 4 5 6 7 1 / q.poll( ) => 2 / q.offer( 2 )
3 4 5 6 7 1 2 / q.poll( ) => 3 출력
<3>4 5 6 7 1 2 / q.poll( ) => 4 / q.offer( 4 )
5 6 7 1 2 4 / q.poll( ) => 5 / q.offer( 5 )
6 7 1 2 4 5 / q.poll( ) => 6 출력
<3 6>7 1 2 4 5 / q.poll( ) => 7 / q.offer( 7 )
1 2 4 5 7 / q.poll( ) => 1 / q.offer( 1 )
2 4 5 7 1 / q.poll( ) => 2 출력
<3 6 2>4 5 7 1 / q.poll( ) => 4 / q.offer( 4 )
5 7 1 4 / q.poll( ) => 5 / q.offer( 5 )
7 1 4 5 / q.poll( ) => 7 출력
<3 6 2 7>1 4 5 / q.poll( ) => 1 / q.offer( 1 )
4 5 1 / q.poll( ) => 4 / q.offer( 4 )
5 1 4 / q.poll( ) => 5 출력
<3 6 2 7 5>1 4 / q.poll( ) => 1 / q.offer( 1 )
4 1 / q.poll( ) => 4 / q.offer( 4 )
1 4 / q.poll( ) => 1 출력
<3 6 2 7 5 1>4 / q.poll( ) => 4 출력
<3 6 2 7 5 1 4>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
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, K;
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
// 출력을 위해 사용
StringBuilder sb = new StringBuilder();
sb.append("<");
// 문제 풀이
// N명의 사람을 넣을 큐 선언
Queue<Integer> q = new LinkedList<>();
// N만큼 반복, 큐에 넣는다.
for (int i = 1; i <= N; i++) {
q.add(i);
}
// 큐가 빌 때까지 반복
while (!q.isEmpty()) {
// K - 1만큼 반복
for (int i = 0; i < K - 1; i++) {
// K 번째 요소가 앞에 오도록
// 맨 앞 요소들을 맨 뒤로 옮긴다.
q.offer(q.poll());
}
// K 번째 요소 출력에 추가
sb.append(q.poll()).append(", ");
}
// 마지막 요소에도 공백이랑 괄호가 들어가기 때문에 제거
sb.delete(sb.length()-2, sb.length());
// 괄호 추가
sb.append(">");
// 출력
System.out.print(sb);
}
}
'Coding > Backjoon' 카테고리의 다른 글
[ Backjoon - 11725번 ] 트리의 부모 찾기 ( java ) (0) | 2023.12.26 |
---|---|
[ Backjoon - 5613번 ] 계산기 프로그램 ( java ) (1) | 2023.12.26 |
[ Backjoon - 10818번 ] 최소, 최대 ( java ) (0) | 2023.11.17 |
[ Backjoon - 1021번 ] 회전하는 큐 ( with java ) (0) | 2023.11.17 |
[ Backjoon - 25556번 ] 포스택 ( with java ) (0) | 2023.11.17 |