[BOJ/Java] 1158 : 요세푸스 문제

문제

www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

풀이

간단한 문제인데도 접근을 잘못해서 너무 복잡하게 하다가 .. 배열 인덱스를 자꾸 벗어나서 망했다. 원래는 큐를 사용하려다가 큐는 인덱스로 접근할 수가 없어서 그냥 ArrayList를 사용했었는데 굳이 인덱스를 사용하지 않아도 k값을 알고 있기 때문에 큐로 더 간단하게 풀 수 있었다.

방법은 다음과 같다.

1. k값은 cnt라는 변수에 저장해준다
2. 큐에서 값을 꺼내고 k번째 사람이 아니면 다시 add해서 맨 뒤로 보내버린다
3. 이 때 cnt--해주며 k번째인 사람을 찾는다
4. k번째 사람을 찾으면 정보를 StringBuilder에 append 해주고 출력 형식을 맞추기 위해 append(", ")도 추가해준다
5. 위 과정을 큐가 빌 때까지 반복한 뒤 StringBuilder의 setLength의 사이즈를 2만큼 빼주어 맨 마지막에 붙은 ", "을 삭제한다

 

코드

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 BOJ1158 {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		Queue<Integer> circle = new LinkedList<>();
		for (int i = 1; i <= n; i++) {
			circle.add(i);
		}

		sb.append("<");
		int cnt = k;
		while (!circle.isEmpty()) {
			int person = circle.poll();
			cnt--;
			if(cnt != 0) circle.add(person);
			else {
				sb.append(person).append(", ");
				cnt = k;
			}
		}
		sb.setLength(sb.length() - 2);
		sb.append(">");
		System.out.println(sb);
	}

}

 

 

느낀점

효율적인 자료구조 사용의 중요성을 느낀다. 원 모양 문제를 풀 때 큐를 사용하는 법도 배웠다. / StringBuilder는 평소에 잘 사용하지 않았는데 이런 출력에서 굉장히 편하다 !