연습문제 2-3(5) 마지막에 남는 사람의 번호 구하기

문제 설명

1번부터 N번까지의 사람이 동그랗게 모여서 앉아있습니다.

1번부터 순서를 세어 K번째 사람을 모임에서 제외시킵니다.

남은 N-1명에서 이번에 제외된 다음 사람부터 원을 따라 다시 순서를 세서 K번째 사람을 모임에서 제외하는 과정을 마지막 사람이 남을 때까지 반복합니다.

이때 마지막으로 남는 사람의 번호를 구하는 프로그램을 구현하세요.

---

입력 형식

· N : 원형으로 모여있는 사람의 수

· K : 매번 제외시킬 사람의 순서

---

출력 형식

· 마지막에 남는 사람의 번호를 정수로 반환

---

입출력 예시

· 입력

  · N = 7

  · K = 3

· 출력 : 4

· 설명 : 1, 2, 3, 4, 5, 6, 7에서 시작하여 3, 6, 2, 7, 5, 1 순서로 제외되어 마지막에는 4번 사람이 남게 된다.

---

작성 코드

class Solution235 {
    public int solution(int N, int K) {
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = i + 1;
        }
        int index = 0;
        while (N > 1) {
            index = (index + K - 1) % N;
            for (int i = index; i < N - 1; i++) {
                arr[i] = arr[i + 1];
            }
            N--;
        }
        return arr[0];
    }

    public static void main(String[] args) {
        Solution235 st = new Solution235();
        int N = 7;
        int K = 3;
        System.out.println(st.solution(N, K));
    }
}

 

정답 코드

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

class Solution {
    public int solution(int N, int K) {
        List<Integer> nums = new ArrayList<>(
                IntStream.range(1, N+1)
                        .boxed()
                        .collect(Collectors.toList())
        );
        int number = 0;
        for (int i = 0; i < N-1; i++) {
            number += K - 1;
            number %= nums.size();
            nums.remove(number);
        }

        return nums.get(0);
    }

    public static void main(String[] args) {
        Solution st = new Solution();
        int N = 7;
        int K = 3;
        System.out.println(st.solution(N, K));
    }
}