[백준] 11866번 : 요세푸스 문제 0 - JAVA [자바]
11866번: 요세푸스 문제 0
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
www.acmicpc.net
- 문제
- 알고리즘 [접근 방법]
큐를 이용한 매우 쉬운 문제다.
예제를 이해해보자면 이렇다. 1부터 N까지 나열 된 수에서 K번째 수 마다 차례대로 뽑아 낸 수열을 출력하는 것이다.
예제를 예로 들어보자.
seq {1, 2, 3, 4, 5, 6, 7}, result {}
round 1 : seq {1, 2, 3, 4, 5, 6, 7}, result {3}
round 2 : seq {1, 2, 4, 5, 6, 7}, result {3, 6}
round 3 : seq {1, 2, 4, 5, 7}, result {3, 6, 2}
round 4 : seq {1, 4, 5, 7}, result {3, 6, 2, 7}
round 5 : seq {1, 4, 5}, result {3, 6, 2, 7, 5}
round 6 : seq {1, 4}, result {3, 6, 2, 7, 5, 1}
round 7 : seq {4}, result {3, 6, 2, 7, 5, 1, 4}
이렇게 삭제된 현재 위치에서 K번 째 수를 찾아 가고, 그 수를 삭제하고.. 이렇게 원소가 남지 않을 때 까지 무한 반복을 하면 되는 것이다.
이 것을 어떻게 큐로 이용해야 할까?
가장 보편적인 방법은 이렇다.
K번 쨰 수가 되기 직전까지 맨 앞의 원소를 K-1 번 꺼내오고(poll) 꺼내온 원소들을 맨 뒤로 넣는다.(offer)
그리고 K번째로 뽑힌(poll) 원소는 출력하면 되는 것이다.
대강 이렇게 보면 된다.
round 1
loop 1 : {1, 2, 3, 4, 5, 6, 7} → {2, 3, 4, 5, 6, 7, 1}
loop 2 : {2, 3, 4, 5, 6, 7, 1} → {3, 4, 5, 6, 7, 1, 2}
loop 3 : {3, 4, 5, 6, 7, 1, 2} → 3 출력
round 2
loop 1 : {4, 5, 6, 7, 1, 2} → {5, 6, 7, 1, 2, 4}
loop 2 : {5, 6, 7, 1, 2, 4} → {6, 7, 1, 2, 4, 5}
loop 3 : {6, 7, 1, 2, 4, 5} → 6 출력
round 3
loop 1 : {7, 1, 2, 4, 5} → {1, 2, 4, 5, 7}
loop 2 : {1, 2, 4, 5, 7} → {2, 4, 5, 7, 1}
loop 3 : {2, 4, 5, 7, 1} → 2 출력
round 4
loop 1 : {4, 5, 7, 1} → {5, 7, 1, 4}
loop 2 : {5, 7, 1, 4} → {7, 1, 4, 5}
loop 3 : {7, 1, 4, 5} → 7 출력
round 5
loop 1 : {1, 4, 5} → {4, 5, 1}
loop 2 : {4, 5, 1} → {5, 1, 4}
loop 3 : {5, 1, 4} → 5 출력
round 6
loop 1 : {1, 4} → {4, 1}
loop 2 : {4, 1} → {1, 4}
loop 3 : {1, 4} → 1 출력
round 7
loop 1 : {4} → {4}
loop 2 : {4} → {4}
loop 3 : {4} → 4 출력
이렇게 가장 간단한 방법으로 알고리즘을 구성할 수 있다. 한마디로 K-1번만큼 poll과 offer을 한 뒤, K번 째 값을 poll만하고 해당 원소를 출력해주면 되는 것이다.
간단하게 코드로 보자면 이렇다.
Queue<Integer> q; // 1~N까지 큐에 입력되어있다고 가정
int K; // K번째 수
while(!q.isEmpty()) {
// K-1번 앞에 있는 원소를 뒤로 보낸다.
for(int i = 0; i < K - 1; i++) {
int val = q.poll();
q.offer(val);
}
print(q.poll()); // K번째로 나오는 원소를 삭제함과 동시에 출력한다.
}
물론 이런 방식 말고 큐 대신 리스트를 활용하여 K값을 매 번 K씩 증가시키며 해당 원소를 삭제하면서 해당 값을 출력하는 방법이 있다.
물론 리스트의 시작 index는 0부터 시작하고, 매 번 원소가 한 개씩 줄기 때문에 때문에 처음 시작 값 및 증가 값은 K값에 -1을 해야한다.
또한 중요한 점은, 참조하려는 인덱스가 입력받은 수보다 작아질 경우가 생기는데, 이럴 경우 참조 범위 밖으로 에러가 생길 수 있다. 그러니 반드시 현재 큐의 크기를 나눈 나머지 값으로 증가시켜야 한다.
위 예제를 그대로 예로들면 이렇다.
index = 2
→ index 2 의 원소 삭제 : {1, 2, 3, 4, 5, 6, 7}
index = 4 [index = (index + (K - 1)) % size → (2 + 2) % 6 = 4]
→ index 4 의 원소 삭제 : {1, 2, 4, 5, 6, 7}
index = 1 [index = (index + (K - 1)) % size → (4 + 2) % 5 = 1]
→ index 1 의 원소 삭제 : {1, 2, 4, 5, 7}
index = 3 [index = (index + (K - 1)) % size → (1 + 2) % 4 = 3]
→ index 3 의 원소 삭제 : {1, 4, 5, 7}
index = 2 [index = (index + (K - 1)) % size → (3 + 2) % 3 = 2]
→ index 2 의 원소 삭제 : {1, 4, 5}
index = 0 [index = (index + (K - 1)) % size → (2 + 2) % 2 = 0]
→ index 0 의 원소 삭제 : {1, 4}
index = 0 [index = (index + (K - 1)) % size → (0 + 2) % 1 = 0]
→ index 0 의 원소 삭제 : {1}
이런 식으로 할 수도 있다.
코드로 보자면 이렇다.
LinkedList<Integer> list; // 1~N까지 리스트에 입력되어있다고 가정
int K; // K번째 수
int index; // 리스트에서 삭제할 요소를 참조할 인덱스
while(!list.isEmpty()) {
index = (index + (K - 1)) % list.size();
print(list.get(index)); // index위치에 있는 요소를 출력
list.remove(index); // index위치에 있는 요소를 삭제
}
- 4가지 방법을 사용하여 풀이한다.
이전 포스팅과 여타 다를 바 없이 아래와 같이 두 가지 입력 방법을 통해 성능을 비교하려 한다.
그리고 각 입력방법에 대해 필자가 설명한 두 가지 방식의 알고리즘을 적용해보도록 하겠다. 출력 내용을 모두 StringBuilder를 사용하여 한 번에 묶은 뒤, 한 번에 출력 할 것이니 이 점 미리 알고계시길 바란다.
1 . Scanner + 알고리즘1
2 . Scanner + 알고리즘2
3. BufferedReader + 알고리즘1
4. BufferedReader + 알고리즘2
- 풀이
- 방법 1 : [Scanner + 알고리즘 1]
import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Queue<Integer> q = new LinkedList<>();
int N = in.nextInt();
int K = in.nextInt();
for(int i = 1; i <= N; i++) {
q.add(i);
}
StringBuilder sb = new StringBuilder();
sb.append('<');
/*
* 마지막 부분의 출력은 > 괄호 전에 공백이 없기 때문에
* 일괄적으로 출력하기 위해 마지막 원소만 남겨질 때까지만
* 반복하고 마지막 원소는 그대로 출력한다.
*/
while(q.size() > 1) {
for(int i = 0; i < K - 1; i++) {
int val = q.poll();
q.offer(val);
}
sb.append(q.poll()).append(", ");
}
// 마지막 원소 출력한 뒤 > 도 붙여준다.
sb.append(q.poll()).append('>');
System.out.println(sb);
}
}
가장 기본적인 방법이라 할 수 있겠다.
중요한 점은 주석으로도 달아놓았지만, 출력 형식을 잘 보면 원소 사이사이에 쉼표(,)와 공백(" ") 이 있지만 마지막 출력 부분은 공백이 없다. 그렇기 때문에 마지막 원소 부분은 반복문으로 돌리지 말고 그 전까지만 반복문을 돌린 뒤, 마지막 원소는 따로 출력해주도록 만들었다.
- 방법 2 : [Scanner + 알고리즘 2]
입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 N과 M을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.
import java.util.Scanner;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
LinkedList<Integer> list = new LinkedList<Integer>();
int N = in.nextInt();
int K = in.nextInt();
for(int i = 1; i <= N; i++) {
list.add(i);
}
StringBuilder sb = new StringBuilder();
sb.append('<');
int index = 0; // 리스트에서 삭제할 요소를 참조할 인덱스 변수
while(list.size() > 1) {
index = (index + (K - 1)) % list.size();
// index위치에 있는 요소를 삭제함과 동시에 출력
sb.append(list.remove(index)).append(", ");
}
// 마지막으로 남은 요소 삭제함과 동시에 출력
sb.append(list.remove()).append('>');
System.out.println(sb);
}
}
리스트 계열 중 어떤 것을 써도 무방하다. 다만 중간 삭제가 많은만큼 ArrayList보다는 약간이나마 LinkedList가 더 효율적이라 LinkedList로 했다.
- 방법 3 : [BufferedReader + 알고리즘 1]
방법 1에서 입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 N과 K를 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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));
Queue<Integer> q = new LinkedList<>();
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
for(int i = 1; i <= N; i++) {
q.add(i);
}
StringBuilder sb = new StringBuilder();
sb.append('<');
/*
* 마지막 부분의 출력은 > 괄호 전에 공백이 없기 때문에
* 일괄적으로 출력하기 위해 마지막 원소만 남겨질 때까지만
* 반복하고 마지막 원소는 그대로 출력한다.
*/
while(q.size() > 1) {
for(int i = 0; i < K - 1; i++) {
q.offer(q.poll());
}
sb.append(q.poll()).append(", ");
}
// 마지막 원소 출력한 뒤 > 도 붙여준다.
sb.append(q.poll()).append('>');
System.out.println(sb);
}
}
입력형식만 바꿔준 것이라 어렵진 않았을 것이다.
- 방법 4 : [BufferedReader + 알고리즘 2]
마찬가지로 방법 2에서 입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다.
만약 매 번 리스트를 참조하여 사이즈를 알아내는 것이 조금 불편하다면 list.size 대신 변수 N을 써서 1씩 감소시켜도 된다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
LinkedList<Integer> list = new LinkedList<Integer>();
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
for(int i = 1; i <= N; i++) {
list.add(i);
}
StringBuilder sb = new StringBuilder();
sb.append('<');
int index = 0; // 리스트에서 삭제할 요소를 참조할 인덱스 변수
while(N > 1) {
index = (index + (K - 1)) % N;
// index위치에 있는 요소를 삭제함과 동시에 출력
sb.append(list.remove(index)).append(", ");
N--;
}
// 마지막으로 남은 요소 삭제함과 동시에 출력
sb.append(list.remove()).append('>');
System.out.println(sb);
}
}
크게 어려울 것은 없을 것이다. 코드도 그리 길지 않고, 조금만 생각해본다면 수식을 금방 완성할 수 있었을 것이다.
- 성능
채점 번호 : 25559256 - 방법 4 : BufferedReader + 알고리즘 2
채점 번호 : 25559252 - 방법 3 : BufferedReader + 알고리즘 1
채점 번호 : 25559249 - 방법 2 : Scanner + 알고리즘 2
채점 번호 : 25559246 - 방법 1 : Scanner + 알고리즘 1
보면 큐에서 매번 원소를 빼고 넣는 것 보다 특정 인덱스를 찾아나서는 것이 훨씬 빠르다는 것을 볼 수 있다.
- 정리
이 번 문제 또한 어려운 점은 없었을 것이다.
큐, 덱을 활용하는 문제지만 다른 방식으로도 더 효율적이게 짤 수 있다는 것을 알려주고자 다른 방법도 보여주었다.
대개 이러한 문제들은 조금만 노트에 정리해보다보면 공식이 어렵지 않게 나오기 때문에 일단 보이는대로 풀이를 해본 뒤 한 번 더 다른 방법은 없는지 고민해보는 것도 좋지 않을까 생각이 든다.
혹여 어렵거나 이해가 되지 않는 부분이 있다면 댓글 남겨주시면 최대한 빠르게 답변드리도록 하겠다.
'JAVA - 백준 [BAEK JOON] > 큐, 덱' 카테고리의 다른 글
| [백준] 1021번 : 회전하는 큐 - JAVA [자바] (0) | 2021.02.27 |
|---|---|
| [백준] 10866번 : 덱 - JAVA [자바] (8) | 2021.02.19 |
| [백준] 1966번 : 프린터 큐 - JAVA [자바] (10) | 2021.02.03 |
| [백준] 2164번 : 카드2 - JAVA [자바] (4) | 2020.12.19 |
| [백준] 18258번 : 큐 2 - JAVA [자바] (6) | 2020.12.13 |