문제 링크

풀이

- 알고리즘 기법을 사용하기보다 테스트 케이스를 기반으로 수학적으로 접근하였다.

- 큐 또는 나머지 연산자를 사용하면 될 거 같다.

public static int saveThePrisoner(int n, int m, int s) {
    return (m % n + s) - 1;
}

- n(죄수의 수), m(과자의 수), s(시작 위치)

- 테스트 케이스 두 개를 기반으로 풀이 했을때 통과하길래 엄청 간단하게 해결한 줄 알고 기뻐했다.

- 하지만 늘 그렇듯이 내게 쉬운 문제는 없었다.

- 주어진 테스트 케이스는 모두 통과하는데 문제 해결이 안 되는 이런 경우가 알고리즘 풀이하면서 제일 난감하다. 스스로 반례를 찾아야 하니 그게 너무 어렵다.

public static int saveThePrisoner(int n, int m, int s) {
    return (m % n + s - 1) % n == 0 ? n : (m % n + s - 1) % n;
}

- 결국 반례를 포인트를 사용해서 보고, 이리 저리 나눠보다가 해결했다.

- 원래 코드의 문제는 (m % n + s) - 1 계산식의 값이 죄수의 보다 큰 경우가 발생하는 문제가 있었다. 그래서 죄수의 수만큼 나머지 연산자로 계산한 후 계산 값이 죄수의 수와 같으면 0이 반환되는데 이경우에는 n의 값이 반환되게끔 변경했다.

- 뭔가 해결하고도 찝찝하다..