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

https://www.acmicpc.net/problem/11866

---

List를 이용한 방법과 Queue를 이용한 방법을 서술하겠다

1. List를 이용한 방법

여담으로 삽입과 삭제가 빈번할 경우 LinkedList가 이론적으로는 좋지만 크게 체감할 정도가 아니며, 이미 코드를 작성했기때문에 아래 코드에는 ArrayList를 사용했다.

자세하게 알고 싶으면 이곳으로...

먼저 ArrayList를 이용하여 순서를 저장한다.

tmp로 삭제할 인덱스를 저장한뒤에  StringBuilder 변수에 ArrayList의 삭제와 동시에 저장을 한다.

위의 과정을 반복하며 ArrayList의 크기가 1이 될때까지 반복문을 돌린 뒤에  출력하면 된다.

 

"7 3"을 입력했을때를 예로 들어보자면

1, 2, 3, 4, 5, 6, 7

tmp = (0+3-1)%7 = 2 

인덱스 [2] 삭제 =>  1, 2, 3, 4, 5, 6, 7

tmp = (2+3-1)%6 = 4

인덱스 [4] 삭제 =>  1, 2, 4, 5, 6, 7

tmp = (4+3-1)%5 = 6%5=1  

인덱스 [1] 삭제 =>  1, 2, 4, 5, 7

.

.

.

위와 같은 과정을 반복한면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		String[] input=br.readLine().split(" ");
		int n=Integer.parseInt(input[0]);
		int k=Integer.parseInt(input[1]);
		ArrayList<Integer> list =new ArrayList<Integer>();
		for(int i=0;i<n;i++) { //리스트에 순서 넣기
			list.add(i+1);
		}
		int tmp=0;
		StringBuilder sb=new StringBuilder("<");
		while (list.size()>1) {//리스트안에 1개만 남을때까지
			tmp=(tmp+k-1)%list.size(); //삭제할 위치 - 나머지연산으로 list의 크기가 넘지 않도록 하기
			sb.append(list.remove(tmp)).append(", "); //삭제와 동시에 StringBuilder에 넣기
		}
		sb.append(list.remove(0)).append(">"); //마지막 요소 넣기
		System.out.println(sb);
	}
}

 

 

2. Queue를 이용한 방법

큐를 이용하면 매우 쉽게 풀 수 있다.

k-1번째까지를 뽑은뒤에 맨 뒤에 삽입하면 맨 앞에 있는 요소가 k번쨰이므로 이것을 StringBuilder 변수에 저장하면 된다.

"7 3"을 입력했을때를 예로 들어보자면

1, 2, 3, 4, 5, 6, 7

k-1번째까지 반복 : 즉 2번

=> 2, 3, 4, 5, 6, 7, 1

     3, 4, 5, 6, 7, 1, 2

     맨 앞에 있는 요소 뽑기 

      3, 4, 5, 6, 7, 1, 2

4, 5, 6, 7, 1, 2

다시 반복

=> 5, 6, 7, 1, 2, 4

     6, 7, 1, 2, 4, 5

     맨 앞에 있는 요소 뽑기 

     6, 7, 1, 2, 4, 5

위의 과정을 반복하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		String[] input=br.readLine().split(" ");
		int n=Integer.parseInt(input[0]);
		int k=Integer.parseInt(input[1]);
		Queue<Integer> que =new LinkedList<Integer>();
		for(int i=1;i<=n;i++) {
			que.add(i);
		}
		StringBuilder sb=new StringBuilder("<");
		while(que.size()>1) {
			for(int i=0;i<k-1;i++) {
				que.add(que.poll());
			}
			sb.append(que.poll()).append(", ");
		}
		sb.append(que.poll()).append(">");
		System.out.println(sb);
	}
}