silver 5. 요세푸스 문제 (1158)

출처 : https://www.acmicpc.net/problem/1158

문제

N명의 사람이 원을 이루며 앉아있고, 양의 정수 K가 주어질 때, 순서대로 K 번째 사람을 제거. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나가고, N명의 사람이 모두 제거될 때까지 반복. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 함

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성

입력: 첫 줄에는 N과 K가 빈 칸을 사이에 두고 순서대로 주어짐 ($1 <= K <= N <= 5,000$)

출력: 요세푸스 순열 출력

풀이

• 아이디어: 연결 리스트(Linked List) 활용. K번째인지 확인해주는 변수를 만들어

  • K번째일 경우, 연결 리스트의 첫 번째 값을 꺼내옴
  • K번째가 아닐 경우, 연결 리스트의 첫 번째 값을 꺼내와 마지막 원소로 다시 넣어줌

    import java.util.*;
    import java.io.*;
  	
    public class Main {
      public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();	// 요세푸스 순열을 저장할 변수
  	
        StringTokenizer st = new StringTokenizer(br.readLine());
        Integer N = Integer.parseInt(st.nextToken());
        Integer K = Integer.parseInt(st.nextToken());
        Integer count = 1;	// K번째인지 확인해줄 변수
  	    
        // 1 ~ N을 가지는 리스트 생성 
        ArrayList<Integer> nums = new ArrayList<Integer>();
        for (Integer i = 0; i < N; i++){
          nums.add(i+1);
        }
  	
        LinkedList<Integer> link = new LinkedList<Integer>(nums);	// 1~N의 값을 가지는 연결 리스트 생성
        while(link.size() > 1) {	// 연결 리스트의 길이가 1보다 클 때
          if(count % K == 0) {	// K번째 수인 경우
            sb.append(link.poll() + ", ");	// 첫 번째 원소의 값을 빼와 요세푸스 순열에 넣어줌
          }
          else {	// K번째 수가 아닌 경우
            link.add(link.poll());	// 첫 번째 원소의 값을 빼와 연결 리스트의 마지막 원소로 넣어줌
          }
          count += 1;	// count 값 1 증가
        }
        sb.append(link.poll());	// 마지막 남은 값을 요세푸스 순열에 넣어줌
        System.out.println("<" + sb + ">");	// 결과 출력
      }
    }
  

  • 마지막 남은 값을 따로 넣어주는 이유는 마지막 값을 넣을 때 ‘, ‘를 요세푸스 순열에 포함시키지 않기 위함