[Leetcode] 1217번 문제 정답과 풀이

coderH·2023년 1월 14일

leetcode

이 문제는 문제를 보고 의도를 파악하기 어려웠던 문제여서 기록을 남기고자 작성합니다.

문제

n개의 칩을 가지고 있으며, i번째 칩의 위치는 position[i]입니다.

모든 칩을 같은 위치로 옮겨야하며 아래와 같이 칩을 옮길 수 있습니다.

position[i] + 2 또는 position[i] - 2은 0의 코스트가 발생
position[i] + 1 또는 position[i] - 1은 1의 코스트가 발생

모든 칩들을 같은 위치로 옮겼을 때 최소 코스트를 구하세요.

제한사항

1 <= position.length <= 100

1 <= position[i] <= 10^9

정답

처음 문제와 제한사항을 봤을 때 칩이 놓일 수 있는 범위는 1~10^9까지로 넓은데 그럼 2이상은 어떻게 계산하라는거지? 라며 문제의 의도를 제대로 파악하지 못했었습니다.

그래서, 여러 사람들의 답변을 보면서 문제의 의도를 파악할 수 있었습니다.

먼저, 배열의 길이는 칩의 개수, 각 요소는 해당 칩이 놓인 위치(인덱스)를 뜻합니다.
만약, 인자가 [2,2,3]이라면 인덱스 2에 칩 2개, 인덱스3에 칩 1개가 놓여집니다.

위에서 말했듯 인덱스 차이가 1이면 1의 비용이, 2이면 0의 비용이 발생하며 최소한의 비용을 사용해 칩들을 모두 한 곳으로 옮겨야만 합니다.

잘 생각해보면 위치가 2칸 떨어진 칩들은 서로간에 옮겨도 어떤 비용도 발생하지 않습니다.
따라서, 칩들을 홀수와 짝수로 나누어 칩들을 모두 한 곳으로 모읍니다.

이 때, 칩들이 어디로 모이는지는 상관없습니다. 최소 비용을 구하는것이기 때문에 홀과 짝의 위치가 한칸만 차이난다고 가정할 수 있습니다.

이후, 이제 비용이 발생하는 한칸의 움직임만 구해주면 됩니다. 홀과 짝 둘 중 더 작은수를 반환하면됩니다.

따라서, 정답 코드는 아래와 같습니다.

const minCostToMoveChips = function(position) {
    let even = 0, odd = 0;
    position.forEach(i => i % 2 === 0 ? even += 1 : odd += 1);

    return Math.min(even, odd);
};

만약, 코드를 더 줄이고 싶다면 아래와 같이 홀과 짝 중 하나만 구한 후 구한 값과 전체에서 이를 뺀 값 중 더 작은 값을 반환하면 됩니다.

const minCostToMoveChips = (position) => {
    const even = position.reduce((p, n) => n % 2 === 0 ? p + 1 : p , 0);
    return Math.min(even, position.length - even);
};