TIL26-04 알고리즘 규칙을 단순화 하자.

문제 설명(공 던지기)

머쓱이는 친구들과 동그랗게 서서 공 던지기 게임을 하고 있습니다. 공은 1번부터 던지며 오른쪽으로 한 명을 건너뛰고 그다음 사람에게만 던질 수 있습니다. 친구들의 번호가 들어있는 정수 배열 numbers와 정수 K가 주어질 때, k번째로 공을 던지는 사람의 번호는 무엇인지 return 하도록 solution 함수를 완성해보세요.

numbers	k	result
[1, 2, 3, 4]	2	3
[1, 2, 3, 4, 5, 6]	5	3
[1, 2, 3]	3	2

풀이 과정

• 잘 못된 풀이 과정
  • 주어진 배열의 길이가 짝수일 때와 홀수일때 다른 규칙을 있을 거라고 접근했다.
  • 그래서인지 규칙이 복잡하게 나왔고, 풀이 과정에 오랜시간이 걸렸다.
  • 하지만 인덱스가 2씩 늘어나는 것은 파악한 상태였다. 하지만 배열의 길이를 벗어난 수의 처리를 어떻게 할지에서 막혔다.
  • 그래서 밑의 코드를 생각했다. 밑의 코드는 두 자리수를 고려하지 않아 틀린 결과를 출력다.

function solution(numbers, k) {
    let a = numbers.join("").repeat(Math.ceil(k/2))
    return Number(a[k*2-2]);    
}

• 규칙을 단순하게한 풀이 과정
  • 인덱스가 2씩 늘어나고, 늘어난 인덱스가 배열의 길이보다 길어지면 배열의 길이만큼 빼면 된다.

function solution(numbers, k) {
    let index = 0 ;
    for(let i = 0; i < k; i++) {
        index += 2;    //인덱스가 2씩 늘어남
        if ( index > numbers.length) {
            index -= numbers.length; //배열의 길이보다 길때 인덱스- 배열의길이를 해준다.
        }
    } return numbers[index -2 ]; //던저준 사람이므로 인덱스 -2
}

• 위처럼 규칙을 정리하고 단순화할 필요성을 느낀 문제였다.
• 위의 코드가 한개의 100% 정답이 안나와 더 간단한 코드를 찾아봤다

function solution(numbers, k) {
    return numbers[(k - 1) * 2 % numbers.length];
}  //k번째 전의 사람이기 때문에 -1 해주고 2씩 늘어가니때문에 곱하기 2를 해주고, 길의로 나눈 나머지가 인덱스 값이 된다.