import java.util.*;

class Solution {

    public int minCostToMoveChips(int[] position) {
        int oddCount = 0;
        int evenCount = 0;

        // 각 위치에 따라 칩의 개수를 세어줍니다.
        for (int pos : position) {
            if (pos % 2 == 0) {
                evenCount++;
            } else {
                oddCount++;
            }
        }

        // 칩들을 모두 짝수 위치나 홀수 위치로 옮기는 비용의 최소값을 반환합니다.
        return Math.min(oddCount, evenCount);
    }
}

이 문제는 칩들을 모두 같은 위치로 이동시키는 데 필요한 최소 비용을 구하는 문제입니다. 각 칩을 position[i] + 2 또는 position[i] - 2로 이동하는 데는 비용이 들지 않고, position[i] + 1 또는 position[i] - 1로 이동하는 데는 비용이 1이 듭니다. 따라서 칩들의 위치가 짝수와 홀수 중에서 더 많이 분포된 쪽으로 칩들을 이동시키는 것이 비용을 최소화하는 데 핵심입니다.

문제를 해결하기 위해 다음과 같은 접근 방식을 사용합니다:

짝수와 홀수 위치의 칩 개수 계산: 칩의 위치가 짝수인 경우와 홀수인 경우의 개수를 각각 세어줍니다.
비용 계산: 모든 칩을 짝수 위치나 홀수 위치로 옮기는 두 가지 경우 중 더 적은 비용을 선택합니다. 이는 짝수 위치의 칩 개수와 홀수 위치의 칩 개수 중 더 작은 값을 반환하면 됩니다. 왜냐하면 칩들을 같은 위치로 옮기는 데 있어서 최소 비용을 계산할 때, 서로 다른 위치에 있는 칩들을 이동시키는 것이므로 적은 개수의 칩들을 이동시키는 것이 더 저렴하기 때문입니다.

이 알고리즘의 시간 복잡도는 배열을 한 번 순회하면서 각 위치의 칩 개수를 세기 때문에 O(n)입니다. 공간 복잡도는 두 개의 변수를 사용하는 것 외에 추가적인 메모리를 사용하지 않으므로 O(1)입니다.

Attempts

처음에는 각 위치에 있는 칩의 개수를 세어 가장 많은 칩이 위치한 곳으로 다른 칩들을 이동시키는 방법으로 접근했습니다:

Solution.java

import java.util.*;
import java.util.Map.*;

class Solution {

    public int minCostToMoveChips(int[] position) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < position.length; i++) {
            map.put(position[i], map.getOrDefault(position[i], 0) + 1);
        }
        
        int maxValue = Integer.MIN_VALUE;
        Integer maxKey = null;
        for (Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > maxValue) {
                maxValue = entry.getValue();
                maxKey = entry.getKey();
            }
        }

        ...
}

이 접근 방식은 각 위치의 칩 개수를 세고, 가장 많은 칩이 있는 위치로 다른 칩들을 이동시키는 방식입니다. 그러나 이 방법은 비효율적이며, 칩을 이동시키는 최적의 방법을 찾지 못합니다. 배열을 반복적으로 순회하면서 각 위치의 칩 개수를 확인하고, 이동 비용을 계산하는 과정에서 시간 복잡도가 높아집니다.

그래서, 다시 생각해보니 칩을 짝수 위치와 홀수 위치로 나누어 최소 비용을 계산하는 것이 문제의 핵심임을 깨달았습니다. 칩을 2씩 이동하는 것이 비용이 들지 않기 때문에, 짝수 위치와 홀수 위치에 있는 칩의 개수를 세어 더 적은 개수의 칩을 이동시키면 된다는 것을 알게 되었습니다. 문제 설명에 힌트가 있는 것을 계속 놓치는 것 같습니다. 앞으로는 문제의 조건과 힌트를 더 주의 깊게 살펴봐야겠습니다.

Algorithm
Greedy