[Leet Code] Minimum Moves to Equal Array Elements II

기면지·2021년 5월 20일

Leet Code algorithm

LeetCode

목록 보기

11/20

안녕하세요!
오늘은 5월 3주차 5번째 알고리즘인 Minimum Moves to Equal Array Elements II 풀이를 작성해보도록 하겠습니다.

문제

요약
주어진 nums 배열에서 해당 숫자들을 동일한 숫자로 만들어야합니다. 그 과정에서 가장 적은 횟수를 return하는 문제입니다.

처음 생각한 방법

우선, nums 배열을 오름차순으로 정렬한 후에 min 값과 max 값 사이 값을 찾아서 횟수를 세주었습니다.
그런데 이 방법이 틀린건지 로직이 틀렸다고 나오더라고요..

두번째로 생각한 방법

그렇다면 가장 최소로 움직여야하니까, 중간 인덱스에 위치한 숫자를 기준으로 횟수를 세주는 방법은 어떨까라는 생각을 했습니다.
아무래도 min 과 max 의 중간 값은 배열에 없는 값일 수도 있지만, 중간 인덱스에 있는 값은 배열에 있는 값이기 때문에 적어도 하나의 숫자는 변화를 주지 않아도 되기 때문입니다.
그래서 length/2 인덱스를 기준삼아서 횟수를 셌고, Accept를 받았습니다.

코드 설명

int result = 0;
Arrays.sort(nums);
int standardNum = nums[nums.length / 2];

결과값을 도출할 result 를 선언합니다.
그리고 배열을 정렬한 후에 기준값을 중간 인덱스의 값으로 설정합니다.

for (int num: nums) {
    result += Math.abs(num - standardNum);
}

그리고 for문을 순회하면서 result 에 num 에서 기준값을 뺀 결과를 절대값으로 더해주면 끝입니다!
여태까지의 문제중에 가장 짧은 코드가 아닐까 생각합니다..

전체 코드

class Solution {
    public int minMoves2(int[] nums) {
        int result = 0;
        Arrays.sort(nums);
        int standardNum = nums[nums.length / 2];

        for (int num: nums) {
            result += Math.abs(num - standardNum);
        }

        return result;
    }
}