문제 설명
요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다.
이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다.
이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.
원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다.
예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
제출 코드
- 실행속도: 372ms
- 메모리: 12096KB
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
static int N, K, size;
static boolean[] survived;
static int[] ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 입력값 입력
N = Integer.parseInt(st.nextToken()); // 사람 수
K = Integer.parseInt(st.nextToken()); // 제거 규칙
survived = new boolean[N + 1]; // 생존 여부를 기록
Arrays.fill(survived, true); // 시작은 모두 생존으로 처리
ans = new int[N]; // 제거된 사람 기록
size = 0; // ans배열의 크기 기록
eliminate();
print();
}
private static void print() {
StringBuilder sb = new StringBuilder();
sb.append('<');
for (int i = 0; i < N; i++) {
if (i < N - 1)
sb.append(ans[i]).append(',').append(' ');
else
sb.append(ans[i]).append('>');
}
System.out.println(sb);
}
private static void eliminate() {
// 첫번째 제거 대상 제거 후 반복작업 수행
int pointer = K;
survived[K] = false;
ans[size++] = K;
// 모두 제거될 때까지 작업 반복
while (size < N) {
int cnt = K; // 포인터 이동횟수 카운터
while (cnt > 0) {
pointer += 1;
if (pointer>N) pointer %= N; // 모듈러 연산
if (survived[pointer]) cnt -= 1; // 포인터가 생존했을 경우에만 카운트 줄임
}
survived[pointer] = false;
ans[size++] = pointer;
}
}
}
1. survived 배열을 이용해 원에서 제거되었는지 여부를 확인
2. ans 배열에 제거된 사람의 번호를 순서대로 저장
3. 이중 while문을 이용해 pointer를 1개씩 움직여가며 조정했다.
1개씩 움직인 이유는 이미 제거된 사람의 번호는 옮긴 횟수에 들어가지 않아야 하기 때문.
개선 코드
- 실행속도: 76ms ← 5배 속도 향상
- 메모리: 12096KB
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
static int N, K, size;
static boolean[] survived;
static int[] ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 입력값 입력
N = Integer.parseInt(st.nextToken()); // 사람 수
K = Integer.parseInt(st.nextToken()); // 제거 규칙
ans = new int[N]; // 제거된 사람 기록
size = 0; // ans배열의 크기 기록
eliminate();
print();
}
private static void print() {
StringBuilder sb = new StringBuilder();
sb.append('<');
for (int i = 0; i < N; i++) {
if (i < N - 1)
sb.append(ans[i]).append(',').append(' ');
else
sb.append(ans[i]).append('>');
}
System.out.println(sb);
}
private static void eliminate() {
int pointer = 0;
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= N; i++) {
list.add(i);
}
while (size<N) {
pointer = (pointer + K - 1) % list.size();
ans[size++] = list.remove(pointer);
}
}
}
주요 개선 사항
1. survived 배열 사용하지 않음.
2. 배열 대신 리스트를 생성하여 사람 제거 시 자동으로 인덱스가 당겨지도록 함.
3. pointer를 K만큼 더해 한번에 움직임
이것이 가능한 이유는 리스트 자료구조를 사용해 알아서 제거된 사람을 걸러주는 역할을 했기 때문!
깨달은 점
리스트를 사용해도 메모리 사용량에 큰 차이가 없었으며, 실행속도도 5배 가량 빨라졌다.
무조건 배열이 실행속도가 빠른 것은 아님을 알게 되었다.
오히려 리스트 자료구조를 사용하여 K만큼 한번에 건너뛸 수 있어 연산량을 많이 줄일 수 있었다.
중간 요소를 제거하거나 새로 삽입할 경우에는 뒤의 요소들을 한번에 당겨주는 리스트 자료구조가 유리함!