Equal

사이트: HackerRank
난이도: 미디움
분류: Dynamic programming

문제

주어진 배열의 원소 값들이 모두 동일한 값이 되기 위한 최소값을 반환하는 문제이다.
해당 문제는 아래 조건을 가지고 있다.

1. 1명을 제외하고 초콜릿을 나눠줄 수 있다.
2. 한번에 나눠줄 수 있는 초콜릿의 개수는 동일해야 한다.
3. 모든 인원이 동일한 개수를 가져야 끝이난다.

문제에서는 한번에 나눠줄 수 있는 초콜릿의 개수를 1, 3, 5개라고 했지만 실제론 1, 2, 5개로 설정하는 것이 맞다.

1. 나의 풀이

어려웠던 점

해당 문제는 조건을 뒤집어서 생각하는 것이 키 인데 거기까지는 생각하지 못했다. 가장 작은 값과 가장 큰 값을 뺀 나머지 중 1, 2, 5 숫자보다 큰 수를 더하는 과정을 반복하려 했었는데 잘 되지 않았다.

[10, 7, 12]
min: 7
max: 12
subtract: 12 - 7 = 5
count: 0

[15, 12, 12]
min: 12
max: 15
subtract: 15 - 12 = 3
count: 1

[15, 14, 14]
min: 14
max: 15
subtract: 15 - 14 = 1
count: 2

[15, 15, 15]
min: 15
max: 15
subtract: 15 - 15 = 0
count: 3

function getMinIndex(arr) {
    return arr.reduce((min, e, i, me) => me[min] > e ? i : min, 0);
}

function getMaxIndex(arr) {
    return arr.reduce((max, e, i, me) => me[max] < e ? i : max, 0);
}

function equal(arr) {
    let count = 0, 
        min = getMinIndex(arr), 
        max = getMaxIndex(arr);

    while(arr[min] !== arr[max]) {
        const subtracted = arr[max] - arr[min];
        const add = subtracted >= 5 
            ? 5
            : subtracted >= 2
                ? 2
                : 1;

        count++;
        arr = arr.map((e, i) => i === max ? e : e + add);
        min = getMinIndex(arr);
        max = getMaxIndex(arr);
    }
    
    return count;
}

몇 개의 테스트케이스에서 시간초과가 되면서 결국 모든 테스트케이스를 통과하진 못했다.

2. 다른사람의 풀이

DP 문제로 나오긴 했으나, DP 없이 풀어도 되는 문제라고 한다.
이 문제는 매 라운드 마다 한명을 제외하고 동일한 개수의 초콜릿을 나눠주지만 역으로 뒤집어서 매 라운드마다 한사람의 초콜릿을 뺏어오는 문제로 해석할 수도 있다고 한다. 알고리즘 문제는 이처럼 조건을 뒤집어서 생각해야 하는 경우가 종종 나오는 것 같다.

먼저 배열의 원소 중 가장 작은 값을 찾는다. 그 후 배열의 모든 원소에서 가장 작은 값을 뺀 나머지들이 뺏어야할 초콜릿의 개수가 된다.

위 내용대로 점화식을 설정하면,

Math.floor(x / 5) + Math.floor((x % 5) / 2) + ((x % 5) % 2);

x는 나머지이다.

탐욕 알고리즘(greedy)을 이용하여 가장 큰 수 인 5를 나눈 몫과 그 나머지의 2를 나눈 몫 + 그 나머지가 되는 것이다.

이것으로 끝이 나는게 아니라 나머지 + (0 ~ 4)를 하여 그 중 가장 적게 나오는 값을 찾아야 한다.

생각보다 복잡하다. 안 풀어보면 시간내로 못 풀 문제라는 생각이 든다.

function solve(x) {
    return Math.floor(x / 5) + Math.floor((x % 5) / 2) + ((x % 5) % 2);
}

function equal(arr) {
    const min = Math.min(...arr);
  	// 나머지 + (0 ~ 4) 들의 결과 값을 저장하기 위해 배열로 선언한다.
    let count = Array(5).fill(0);
    
    arr.forEach(e => {
      	// 나머지 + (0 ~ 4) 값들을 처리하기 위해 loop를 돈다.
        for (let i = 0; i < 5; i++) {
            const sub = e - (min - i);
            count[i] += solve(sub);
        }
    });
    
    return Math.min(...count);
}

결론

DP 문제였으나, 다른 방식으로 푸는 것이 더 간단한 문제였다. 괜히 알고리즘 카테고리에 신경써서 고민하는 상황을 줄여야 할 것 같다.