[자료구조] 백준 - 요세푸스 문제 0

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

11866번: 요세푸스 문제 0

 

-문제해설

어레이리스트를 이용해서 출력해야될 인덱스를 StringBuffer에 저장시키고 리스트에서 삭제시킨다.

이를 계속반복하면서 리스트가 비워지면 반복문을 빠져나오고 저장된 StringBuffer를 출력한다.

 

이때 인덱스값 설정할 때 조금 애먹었다.. idx를 인덱스변수라고 하면 처음에 0으로 선언한다.

그리고 idx + (k+1)에다가 리스트 크기로 나눈 나머지를 idx로 설정한다.

( idx + (k+1) ) % arr.size()

 

arr.size()가 7이고 k가 2라고 하면

arr = [ 1, 2, 3, 4, 5, 6, 7 ] 

idx = 0 --> ( 0 + (2-1) ) % 7 = 1 % 7 = 1  ---> arr[idx] = 2  ---> arr.remove( idx )  => arr= [ 1, 3, 4, 5, 6, 7 ]

idx = 1 --> ( 1 + (2-1) ) % 6 = 2 % 6 = 2 ---> arr[idx] = 4   ---> arr.remove( idx )  => arr= [ 1, 3, 5, 6, 7 ]

idx = 2 --> ( 2 + (2-1) ) % 5 = 3 % 5 = 2  ---> arr[idx] = 6  ----> arr.remove( idx )  => arr= [ 1, 3, 5, 7 ]

idx = 3 --> ( 3 + (2-1) ) % 4 = 4 % 4 = 0  ---> arr[idx] = 1  ----> arr.remove( idx )  => arr= [ 3, 5, 7 ]

idx = 4 --> ( 4 + (2-1) ) % 3 = 5 % 3 = 2  ---> arr[idx] = 5  ----> arr.remove( idx )  => arr= [ 3, 7 ]

idx = 5 --> ( 5 + (2-1) ) % 2 = 6 % 2 = 0  ---> arr[idx] = 3  ----> arr.remove( idx )  => arr= [ 7 ]

idx = 6 --> ( 6 + (2-1) ) % 1 = 7 % 1 = 0  ---> arr[idx] = 7  ----> arr.remove( idx )  => arr= [  ]

 

큐를 이용해서 풀 수도 있다. 큐를 이용한 풀이는 아래 블로그에 정리가 잘 되어 있다.

https://st-lab.tistory.com/197

 

k번째 수를 출력해줘야하므로 k-1번째까지 큐의 맨 앞에 있는 값을 pop시키고 다시 add시키는 과정을 반복하고

k번째에 도착하면 큐 안의 k번째 값을 pop시킨다. 이를 계속반복하다가 큐의 원소가 1개 남았을 때 반복문을 빠져나가고 남은 원소도 pop시켜서 출력시키면 된다.

 

n =7, k = 3일 때

1 2 3 4 5 6 7

2 3 4 5 6 7 1

3 4 5 6 7 1 2 (k-1번째)

q.pop()

4 5 6 7 1 2 

5 6 7 1 2 4

6 7 1 2 4 5 (k-1번째)

q.pop()

7 1 2 4 5

1 2 4 5 7

2 4 5 7 1 (k-1번째)

q.pop()

4 5 7 1  이를 반복한다.

 

 

파이썬은 큐를 이용해서 풀었다.

 

 

 

-자바( 배열 이용 )

package dataStructure;

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

public class BJ11866 {
	private static ArrayList<Integer> arr = new ArrayList<Integer>();
	private static int idx;		//arr에서 값을 뽑아내기위한 인덱스값
	private static int k;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer( br.readLine() );
		int n = Integer.parseInt( st.nextToken() );
		k = Integer.parseInt( st.nextToken() );
		
		idx = 0;
		
		//1부터 n까지 리스트에 삽입
		for( int i=1; i<=n; i++ ) arr.add( i );
		
		//최종 출력에 사용될 StringBuffer
		StringBuffer sb = new StringBuffer(); 
		sb.append( "<" );
		
		while( true ) {	//arr가 비어있지 않으면 계속 반복
			
			idx = ( idx + (k-1) ) % arr.size();
			sb.append( arr.get( idx ) );
			arr.remove( idx );
			
			if( arr.isEmpty() ) break;
			sb.append( ", " );
		}
		
		sb.append( ">" );
		System.out.println( sb );
	}
}

 

 

-자바( 큐 이용 )

package dataStructure;

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer( br.readLine() );
		int n = Integer.parseInt( st.nextToken() );
		int k = Integer.parseInt( st.nextToken() );
		
		Queue<Integer> q = new LinkedList<Integer>();
		
		for( int i=1; i<=n; i++ ) q.add( i );
		
		StringBuffer sb = new StringBuffer();
		sb.append( "<" );
		
		while( q.size() > 1 ) {
			for( int i=0; i<k-1; i++ ) q.offer( q.poll() );
			
			sb.append( q.poll() ).append( ", " );
		}
		
		sb.append( q.poll() ).append( ">" );
		System.out.println( sb );
	}
}

 

 

 

-파이썬

 

import sys
from collections import deque
l = sys.stdin.readline
n, k = map(int, l().split())

q = deque()
for i in range( 1, n+1 ): q.append( i )

s = "<"

while len(q) > 1:
    for _ in range( k-1 ): q.append( q.popleft() )
    s += str( q.popleft() )+", "
    
s += str( q.popleft() )+">"
print( s )