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

#1 코드

#1-1 자바

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        String[] testCase = sc.nextLine().split(" ");
        int N = Integer.parseInt(testCase[0]);
        int K = Integer.parseInt(testCase[1]);
        
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        for(int i = 1; i <= N; i++) {
            arrayList.add(i);
        }
        
        ArrayList<Integer> josephus = new ArrayList<Integer>();
        
        int nowIndex = -1; // 유일하게, 첫 시행에서만 "K을 더한 인덱스"라는 규칙이 아니라 "K번째 인덱스"라는 규칙을 사용한다. 따라서, 0이 아니라 -1를 대입한다.
        for(int maxIndex = (N - 1); maxIndex >= 0; maxIndex--) {
            nowIndex = calculateNextIndex(nowIndex, maxIndex, K);
            
            josephus.add(arrayList.get(nowIndex));
            arrayList.remove(nowIndex);
            nowIndex--; // nowIndex 값을 인덱스로 가지는 arrayList의 원소가 삭제되었으므로, nowIndex도 하나 줄인다. (동기화)
        }
        
        String submit = "<";
        for(int element : josephus) {
            submit += Integer.toString(element) + ", ";
        }
        submit = submit.substring(0, submit.length() - 2) + ">";
            
        System.out.println(submit);
    }
    
    private static int calculateNextIndex(int nowIndex, int maxIndex, int step) {
        int nextIndex = nowIndex + step;
                
        while(maxIndex < nextIndex) {
            /*
            {&, %, @, #, *, +, -}
            nowIndex = 4 (*)
            maxIndex = 6 (-)
            step = 5
        
            nowIndex + step 은 @여야 함 (@의 인덱스는 2)
            nowIndex + step = 4 + 5 = 9
            9가 2가 되기 위해선 7을 빼야한다.
            7 = maxIndex + 1
            */
            nextIndex -= (maxIndex + 1);
            
        }
            
        return nextIndex;
    }
}

 

#1-2 코틀린

fun main() {
    val testCase = readln().split(" ")
    val N = testCase[0].toInt()
    val K = testCase[1].toInt()

    val arrayList : ArrayList<Int> = ArrayList()
    for(i : Int in 1..N) {
        arrayList.add(i)
    }

    val josephus : ArrayList<Int> = ArrayList()

    var nowIndex = -1 // 유일하게, 첫 시행에서만 "K을 더한 인덱스"라는 규칙이 아니라 "K번째 인덱스"라는 규칙을 사용한다. 따라서, 0이 아니라 -1를 대입한다.
    for(maxIndex : Int in (N - 1) downTo 0) {
        nowIndex = calculateNextIndex(nowIndex, maxIndex, K)

        josephus.add(arrayList[nowIndex])
        arrayList.removeAt(nowIndex)
        nowIndex-- // nowIndex 값을 인덱스로 가지는 arrayList의 원소가 삭제되었으므로, nowIndex도 하나 줄인다. (동기화)
    }

    var submit = "<"
    for(element in josephus) {
        submit += "${element}, "
    }
    submit = submit.substring(0, submit.length - 2) + ">"

    println(submit)
}

fun calculateNextIndex(nowIndex : Int, maxIndex : Int, step : Int) : Int {
    var nextIndex = nowIndex + step

    while(maxIndex < nextIndex) {
        /*
        {&, %, @, #, *, +, -}
        nowIndex = 4 (*)
        maxIndex = 6 (-)
        step = 5
        
        nowIndex + step 은 @여야 함 (@의 인덱스는 2)
        nowIndex + step = 4 + 5 = 9
        9가 2가 되기 위해선 7을 빼야한다.
        7 = maxIndex + 1
        */
        nextIndex -= (maxIndex + 1)
    }

    return nextIndex
}