[백준 Java] 1158번 요세푸스 문제 ( 구현 )

 

[Silver IV] 요세푸스 문제 - 1158

문제 링크

성능 요약

메모리: 15204 KB, 시간: 136 ms

분류

자료 구조, 구현, 큐

문제 설명

요세푸스 문제는 다음과 같다.

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)

출력

예제와 같이 요세푸스 순열을 출력한다.

💡 나의 접근

https://www.acmicpc.net/group/practice/16685

로그인

반전요세푸스 먼저 풀게 되었고 한번에 통과하지 못하고 어디가 문제인지 몰라서 부분적으로 제대로 통과하는지 알아보고자 이 문제를 풀게 되었다.

이 문제를 통과했다면 위 문제도 풀어보길 바란다.

아마도 금방 풀 수 있을듯?

 

나는 자료구조를 ArrayList를 사용했다.

N의 크기를 봤을때 5000밖에 되지 않았고 N^2도 가능할 것 같아서 

for문을 이용해서 idx를 1씩 증가시켜 K번만큼 반복하는데

이때 idx가 남아있는 숫자의 갯수를 넘어간다면 idx=0으로 두어 원형으로 탐색할 수 있게 하였다.

그렇게 해서 제거할 인덱스(idx)를 알아낸 후 Arraylist에서 제거하였다.

 

큐를 써야하는 문제인지는 알고리즘 분류를 보고서야 알았다 ㅋㅋㅋㅋㅋ

아직은 생각해내는 자료구조가 한정적인가보다

뭐.. 아무렴 어때 

문제가 풀리기만 하면 됐지 ㅋㅋㅋㅋ

 

아, 심지어 큐를 사용한 코드보다 시간은 훨신 짧은거 같다.

 

 

 

💡 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int K;
	static ArrayList<Integer> num = new ArrayList<>();
	static StringBuilder sb = new StringBuilder();
	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());


		for (int i = 1; i <= N; i++) {
			num.add(i);
		}
		sb.append("<");
		Josephus(-1);
		sb.delete(sb.length()-2,sb.length());
		sb.append(">");

		System.out.println(sb.toString());

	}
	static void Josephus(int idx) {
		int count =0;
		while (!num.isEmpty()) {
			for (int i = 0; i < K; i++) {
				idx ++;
				if(idx >= num.size()) {
					idx = 0;
				}
			}
			sb.append(num.get(idx)).append(", ");
			num.remove(idx--);
		}

	}

}