메모

해결법

방법 1

import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
        
		Queue<Integer> q = new LinkedList<>();
		
		int N = in.nextInt();		// 사람 수
		int K = in.nextInt();		// 제거할 ?번째
		
        // q 에 사람 수 만큼 입력한다
		for (int i = 1; i <= N; i++) {
			q.add(i);
		}
		
        // 요세푸스 순열을 담을 sb
		StringBuilder sb = new StringBuilder();
		sb.append('<');
		
		/*
		 *  마지막 부분의 출력은 > 괄호 전에 공백이 없기 때문에
		 *  일괄적으로 출력하기 위해 마지막 원소만 남겨질 때까지만
		 *  반복하고 마지막 원소는 그대로 출력한다.
		 */
		while (q.size() > 1) {			// 매 루프마다 q 의 크기 판단
			for (int i = 0; i < K - 1; i++) {
				int val = q.poll();		// 가장 앞의 원소를 꺼내서
				q.offer(val);			// 이 원소를 가장 뒤로 넣는다
			}
			
			sb.append(q.poll()).append(", ");		// k 번째는 sb에 담는다
		}
 
		// 마지막 원소 출력한 뒤 > 도 붙여준다.
		sb.append(q.poll()).append('>');
		System.out.println(sb);
	}
 
}

• Queue(큐)

  • 방법

    • 가장 앞의 원소를 꺼내서(poll)
    • 이 원소를 가장 뒤로 넣는다(offer)
    • poll -> offer 을 반복하다가, k번째가 가장 앞에 위치할 때 해당 원소를 출력

  • 예시

    • 

• (N, K)-요세푸스 순열
  <1, 2, 3, 4, 5, 6, 7>

• size() : 컬렉션 프레임워크 타입의 길이를 알고자 할 때 사용

  참고: length, length(), size()

• sb.append(q.poll()).append(", ");

  • 쉼표(,)와 공백이 있음
    • 다음 원소를 넣어야하기 때문
  • sb.append(q.poll()).append('>');
    • 따라서, 해당 코드는 while반복문 밖에 있음

요세푸스 문제 0 (백준 11866번)