BOJ
[BOJ] [JAVA] 11866번 요세푸스 문제0
Parsler
2024. 1. 10. 23:25
Queue 큐 자료구조를 처음 배웠다.
이번 문제를 풀면서 큐를 이렇게 쓸 수 있구나 하는게 신기해서 적어본다.
https://www.acmicpc.net/problem/11866
11866번: 요세푸스 문제 0
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
www.acmicpc.net
문제에서는 원순열을 만들고,
원순열의 원소를 규칙대로 제거하면서, 제거된 원소 순서대로 출력하라고 한다.
이 원순열을 큐 자료 구조로 구현할 수 있다.
큐의 가장 앞 원소를 저장하고, 제거한 후
저장된 원소를 큐의 가장 뒤에 집어넣음으로 원순열이 구현된다.(신기하다 ㅋㅋ)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Queue<Integer> queue = new LinkedList<>();
int n = sc.nextInt();
int k = sc.nextInt();
sc.close();
for (int i = 1; i <= n; i++) {
queue.offer(i);
}
int tmp = 1;
StringBuilder sb = new StringBuilder();
sb.append("<");
while (queue.size() > 1) {
if (tmp % k == 0) {
sb.append(queue.peek()).append(", ");
queue.poll();
} else {
int a = queue.peek();
queue.poll();
queue.offer(a);
}
tmp++;
}
sb.append(queue.peek()).append(">");
System.out.println(sb);
}
}
큐 사용 방법만 알면 간단하게 해결할 수 있다.
tmp가 k의 배수가 될 때 stringbuilder에 넣는 방식으로 해결했다.
너무 졸려