[Java] 김신 장군 살리기

김신 장군 살리기

전쟁에서 처참한 패배를 겪고 돌아온 김신 장군. 책임을 지기 위해 살아 돌아온 이들에게 자결을 제안하는데...

n명의 군사들이 동그랗게 서있고, 한 명씩 세어 나가서 매 k 번째 사람이 죽기로 합니다.

예를 들어서 8명의 군사들이 있고 3명마다 죽기로 하면 이 순서로 군사들이 죽게 됩니다.

 

3 => 6 => 1 => 5 => 2 => 8 => 4 => 7

 

하지만 야비한 김신 장군은 자신이 마지막으로 남아서 도망가려는 속셈인데요. 파라미터로 정수 n과 정수 k를 받고, 김신 장군이 살기 위해 서있어야할 자리(int)를 리턴해주는 메소드 getSurvivingIndex를 쓰세요.

ArrayList를 사용하세요!

템플릿

 

import java.util.ArrayList;

public class Main {
    public static int getSurvivingIndex(int n, int k) {
        // 코드를 입력하세요.
    }

    public static void main(String[] args) {
        System.out.println("김신은 " + getSurvivingIndex(20, 5) + "번 자리에 서있으면 됩니다.");
    }
}

 

5번 군사가 죽습니다.
10번 군사가 죽습니다.
15번 군사가 죽습니다.
20번 군사가 죽습니다.
6번 군사가 죽습니다.
12번 군사가 죽습니다.
18번 군사가 죽습니다.
4번 군사가 죽습니다.
13번 군사가 죽습니다.
1번 군사가 죽습니다.
9번 군사가 죽습니다.
19번 군사가 죽습니다.
11번 군사가 죽습니다.
3번 군사가 죽습니다.
17번 군사가 죽습니다.
16번 군사가 죽습니다.
2번 군사가 죽습니다.
8번 군사가 죽습니다.
14번 군사가 죽습니다.
김신은 7번 자리에 서있으면 됩니다.

 

 

 

힌트 1

getSurvivingIndex 메소드 내에서 soldiers 배열을 생성하고, 파라미터 n만큼의 군사를 채워넣는 코드는 아래와 같다.

이 문제의 관건은 killIndex를 적절히 설정하여, soldiers 배열의 원소가 한 개가 될 때까지 군사들을 배열에서 제거하는 것이다.

 

public static int getSurvivingIndex(int n, int k) {
    ArrayList<Integer> soldiers = new ArrayList<>();

    for (int soldierNumber = 1; soldierNumber <= n; soldierNumber++) {
        soldiers.add(soldierNumber);
    }

    // killIndex를 설정하여, 김신 장군이 혼자 남을 때까지 군사들을 자결시키기.
    // 코드를 작성하세요.
}

 

힌트 2

getSurvivingIndex(20, 5)이 호출됐다고 가정하면, 20명이 동그랗게 서있고, 매 5번째 사람이 자결하는 것이다.

먼저 killIndex의 초기값을 0으로 설정해주고, 배열의 인덱스는 0부터 시작하기 때문에, 5번째 군사는 인덱스 4에 위치해 있습니다. 따라서 killIndex를 4 (= 5 - 1)만큼 증가시키고, 해당 원소를 제거해주자.

이후 10번째 군사를 제거하기 위해 killIndex를 5만큼 늘려야할 것처럼 생각이 들지만 실상은 이와 다르다.

아래 정리한 내용에서 보실 수 있듯이, 인덱스 4의 원소를 제거하면 배열의 크기가 1만큼 줄어든다.

이로써 10번째 군사는 인덱스 8에 위치하게 되고 따라서 killIndex를 역시 4 (= 5 - 1)만큼 증가시키고, 해당 원소를 제거해주어야 하는 것이다. 이를 일반화하면, killIndex를 매번 k - 1만큼 증가시켜주어야 한다는 결론이 나온다.

 

1 -> 인덱스 0
2 -> 인덱스 1
3 -> 인덱스 2
4 -> 인덱스 3
5 -> 인덱스 4 -> 제거
6 -> 인덱스 5 -> 인덱스 4
7 -> 인덱스 6 -> 인덱스 5
8 -> 인덱스 7 -> 인덱스 6
9 -> 인덱스 8 -> 인덱스 7
10 -> 인덱스 9 -> 인덱스 8 -> 제거
11 -> 인덱스 10 -> 인덱스 9 -> 인덱스 8
12 -> 인덱스 11 -> 인덱스 10 -> 인덱스 9
13 -> 인덱스 12 -> 인덱스 11 -> 인덱스 10
14 -> 인덱스 13 -> 인덱스 12 -> 인덱스 11
15 -> 인덱스 14 -> 인덱스 13 -> 인덱스 12 -> 제거
16 -> 인덱스 15 -> 인덱스 14 -> 인덱스 13 -> 인덱스 12
17 -> 인덱스 16 -> 인덱스 15 -> 인덱스 14 -> 인덱스 13
18 -> 인덱스 17 -> 인덱스 16 -> 인덱스 15 -> 인덱스 14
19 -> 인덱스 18 -> 인덱스 17 -> 인덱스 16 -> 인덱스 15
20 -> 인덱스 19 -> 인덱스 18 -> 인덱스 17 -> 인덱스 16 -> 제거

 

그런데 만약 killIndex가 전체 배열의 크기(soldiers.size())를 넘어서면 어떻게 해야할까?

그럴 때는 killIndex가 마지막 인덱스에서 0번째 인덱스로 다시 순환되게끔 해주어야 한다.

원형으로 서있기 때문에, 고리처럼 끝점과 시작점이 이어진다고 상상해보자. 이를 해결하기 위한 가장 좋은 방법은 killIndex를 전체 배열의 크기(soldiers.size())로 나눈 나머지로 재지정해주는 것이다.

예를 들면, 20번째 장군(인덱스 16)을 제거한 후에는 배열의 크기가 16이 되고, killIndex = 16 + 4가 되어 배열의 크기보다 커지게 된다. killIndex(다음 killIndex) = (16(현재 killIndex) + 4(파라미터 k - 1)) % 16(배열의 크기)로 지정해줌으로써, killIndex = 4가 되고, 4번 인덱스에 서있는 6번 군사가 죽게 되는 것이다.

 

코드 작성

코드 작성 1

코드 작성 2