[백준 11866] 요세푸스 문제 0

문제

11866번: 요세푸스 문제 0

 

접근법

1. 수열에서 삭제한 숫자를 요세푸스 수열에 넣는다.

 * 이때 수열에서 삭제를 하게 될 때, 삭제 이후의 요소들이 자동으로 땡겨지게 하여야 하므로 ArrayList를 이용해 수열을 구현한다.

* 삭제할 숫자를 가르키는 pointer 변수를 만든다.

* 입력 받은 K는 그 다음 요세푸스 숫자를 가르키기 위한 숫자로 K=3이면 삭제한 숫자에서 3 떨어진 위치의 숫자가 요세푸스 숫자가 된다.

 

2. 수열에서 숫자를 삭제하게 되면 뒤에 있는 요소가 앞으로 땡겨지기 때문에 현재 pointer가 +1 이 된다. 따라서 그 다음 요세푸스 숫자를 가리키기 위해 pointer+(K-1)을 한다.

 

3. 이때 pointer가 숫자배열의 크기를 넘어가게 되는 경우가 생기는데 나머지 연산을 이용해서 유효한 포인터로 바꾼다. 

 

코드

 

package queue;

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Scanner;

public class Jo4 {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = in.nextInt();
		int K = in.nextInt();
		
		ArrayList<Integer> numArray = new ArrayList<Integer>();
		int[] joArray = new int[N];
		
		for(int i=1; i<=N; i++) {
			numArray.add(i);
		}
		
		int ptr=0;
		int index=0;
		StringBuilder sb = new StringBuilder();
		sb.append("<");
		
		for(int i=0; i<joArray.length;i++) {
			int max = numArray.size();
			ptr=index;
			ptr+=(K-1);
			
			index=ptr%max;
			
			joArray[i] = numArray.remove(index);
			sb.append(joArray[i]+", ");
		}
		
		sb.delete(sb.length()-2, sb.length());
		sb.append(">");
		System.out.println(sb);
		
		
		
		

	}
}

 

 

comment

이 문제가 왜 큐로 분류되어 있는지 모르겠다.