프로그래머스 Lv.0 | 공던지기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/120843

 

 

💻 코드

풀이 1

'오 이건 원형리스트고 맨 앞에가 공 던지는 사람이 되도록 배열을 2개씩 shift, push, shift, push 반복하면 되겠다!' 하고 냅다 풀었는데 너무 날것이라 내가 생각해도 좀 웃김

function solution(numbers, k) {
    for(let i = 1; i <= k; i++) {
        if(i === k) return numbers[0];
        numbers.push(...numbers.splice(0, 2));
    }
}

 

풀이2 - 개선한 버전

패턴을 좀 찾아보자.

numbers = [1, 2, 3, 4], k = 3 인 경우

0, 2, 4번 인덱스가 공을 던진다. 하지만 4번 인덱스라는 게 없으므로 0번으로 돌아가게 된다.

무한순환소수에서 n번째 자리 숫자를 알아내는 방법이 n % 반복되는 수의 길이번째 인 것 처럼

4 % numbers.length -> 0번째 수인 1 이라는 결과가 나오는 것이다.

 

그러면 4번째 인덱스가 최종적으로 공을 던진다는 것을 어떻게 하면 한번에 알 수 있을까? 공을 건너뛰어서 던지지 않고 바로 옆자리 사람에게 패스하면 [3-1] 인덱스의 사람이 마지막으로 던졌을 텐데 (3번째 사람이긴 한데 인덱스로 따지면 1을 뺀 [2]다) 두사람씩 건너뛰었으므로 [(3-1) * 2] 인덱스의 사람이 마지막으로 던졌을 것이다.
이를 일반화하면 [(k-1) * 2] 인덱스가 최종적으로 던진 것이고, 앞에서 생각했던 배열의 범위를 넘었을 경우를 적용하면 

[(k-1) * 2 % numbers.length] 인덱스가 마지막으로 던졌다는 것을 알 수 있다.

function solution(numbers, k) {
    return numbers[(k - 1) * 2 % numbers.length];
}

 

+) 이 밖에도 반복문으로 0부터 k까지 i += 2 를 돌며, 만약 i가 배열의 범위를 넘겼을 경우에는 다시 i - numbers.length번째로 돌아가도록 해서 풀 수 있기도 하다. 근데 그건 1번 풀이에서 배열 연산을 이용한 것보다 메모리가 적게 든다 뿐이지 푸는 원리는 같음. 2번 풀이처럼 패턴을 찾아 한번에 해결하도록 사고하도록 연습해야겠음.