[HackerRank] Save the Prisoner! - Java

문제 설명

 

Save the Prisoner! | HackerRank

 

 

풀이 1 : Fail(시간 초과)

소스 코드

    public static int saveThePrisoner(int n, int m, int s) {
        // Write your code here
        int num = s-1;
        for (int i = 0; i < m; i++) {
            num++;
            if(num > n)
                num = 1;
        }
        return num;
    }

 

풀이 회고

이 문제에서는 n명의 죄수와 m개의 사탕이 주어졌을 때 죄수번호 1 ~ n 죄수 중 죄수 번호 s(1<=s<=n)부터 오름차순(n 초과 시 다시 1부터 시작)으로 사탕을 배급하였을 때 마지막으로 사탕을 받은 죄수 번호를 요구하고 있다.

 

이 문제를 풀기위해 먼저 각각의 죄수에 대한 사탕 배급은 사탕의 개수만큼 이루어지므로 for 문을 통해 m회의 순회가 일어나도록 했다. 이때 현재 죄수 번호(num)에 1씩 증가시켜주었고 최대 죄수 번호인 n을 초과하게 되면 다시 1로 되돌아가도록 구현했다. 다만, 최초 사탕 배급 시 해당 죄수 번호 자체를 가리켜야 하므로 num을 s - 1로 초기화시켜주었다.

 

하지만 위 풀이는 우선 문제에서 주어진 n과 m의 조건을 보지 못했을 때 풀이한 방식이다. n과 m은 각각 10억이다. 즉 위와 같은 방식으로 풀이하다보면 최악의 경우 10억번의 for문 순회를 테스트 횟수 t(최대 100)만큼 계속 반복해야하는 것이다. 즉, 이 문제는 for문 순회를 통해 문제에 접근하면 안 되고 특정 연산만으로도 결과값을 도출할 수 있었어야 했다.

 

 

풀이 2 : Success

소스 코드

    public static int saveThePrisoner(int n, int m, int s) {
        // Write your code here
        return (s+m-1)%n != 0 ? (s+m-1)%n : n;
    }

 

풀이 회고

그리하여 for문을 제거하고 어떤 규칙성을 발견하고자 했다. 예를 들어, 4명의 죄수와 6개의 사탕이 주어진 상황에서 죄수 번호 2번 부터 사탕을 배급한다고 가정해보면 다음과 같은 상황을 상상해볼 수 있다.

 

죄수 번호 1~4의 죄수들과 사탕(별) 배급 현황

 

최초 배급 대상 죄수번호(s)인 2 번부터 사탕의 총 개수(m)만큼 사탕이 일직선상으로 순차적으로 배급됨으로써 죄수 번호 2번부터 순차적으로 사탕을 배급했더니 최종적으로 죄수 번호 3번에게 마지막 사탕이 주어진 것을 확인할 수 있다. 이때 최초 배급 대상 죄수 번호 2와 사탕 총 개수 6을 덧셈(+)하고 1을 뺄셈(-)면 7(=2+6-1)이 나오는데 이는 맨 앞에 있는 죄수 번호 1부터 마지막 사탕을 배급받은 죄수번호 3까지의 죄수 수와 같다. 이때 1을 뺀 이유는 최초 배급 대상 죄수 번호 2가 사탕을 받은 것이 중복 가산되기 때문이다.

 

이 7이라는 숫자에 전체 죄수의 수 4를 나머지(%) 연산하면 3이 나오는데 이는 마지막으로 사탕을 배급받은 죄수 번호 3과 일치하는데 그 이유는 나머지(%) 연산을 통해 이미 지난 죄수 사탕 배급 사이클을 모두 제거 시켜주기 때문이다. 문제에서 요구하는 것은 현재 사이클에서 마지막으로 사탕을 받은 죄수 번호이다.

 

다만 마지막으로 사탕을 배급받는 죄수 번호가 죄수 사이클의 마지막에 위치하면 나머지 연산 시 0을 반환하므로 해당(마지막) 죄수 번호를 가리키는 n을 결과값으로 출력하도록 했다.