[Programmers]야근 지수

https://programmers.co.kr/learn/courses/30/lessons/12927

코딩테스트 연습 - 야근 지수

---

  위 문제를 간단히 요약하자면 배열의 각 요소들을 총 n번 빼고 뺀 결과들의 제곱의 합이 최소가 되기 한다. 이때 숫자가 클 수록 제곱을 했을 때 변화량이 크기 때문에 배열의 각 값들이 고르게 분포되도록 값을 빼주어야 한다. 즉, 매번 배열에서 가장 큰 숫자를 골라 -1해주는 것이 좋다.

 

function solution(works, n) {
  const sum = works.reduce((acc, cur) => acc + cur);
  if (sum < n) return 0; //시간 안에 모든 작업이 끝나는 경우 0

  const workResults = [...works];
  for (let i = 0; i < n; i++) {
    const [max, idx] = workResults.reduce((acc, cur, idx) => {//최대 값의 idx 구하기
      if (acc[0] < cur) return [cur, idx];
      return acc;
    }, [workResults[0], 0]);
    workResults[idx] = max - 1; //최대 값을 -1한다.
  }
  return workResults.reduce((acc, cur) => acc + cur ** 2, 0); //제곱의 합
}

  위의 풀이를 코드로 쓰면 위와 같다. 먼저 시간 안에 모든 작업이 끝나는 경우를 제외시킨다. 그 후 계속 배열에서 최대 값을 찾아 -1해주는 것이다. 그러나 위 코드는 n * works.length 만큼 연산이 수행된다. 즉, n이 최대값인 100만이고, works이 최대 길이인 2만인 경우 200만의 연산을 수행하게 되어 시간초과가 발생한다. 

 

  위 코드의 실행 시간을 감소시키기 위해서는 -1하는 n번의 연산을 줄이거나 배열에서 최대 값을 찾는 works.length 번의 연산을 줄여야한다. 나는 매번 배열에서 최대 값을 찾지 않고 항상 0번 위치에 최대값이 존재하는 최대 힙을 이용하여 구현해보려 한다. 최대 힙에 대해서는  이전 포스팅을 참조하자.

 

function solution(n, works) {
  let sum = works.reduce((acc, cur) => acc + cur);
  if (sum < n) return 0;

  const heap = [];
  const swap = (idx1, idx2, arr) => { //2개의 배열요소 교환
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  }
  const getParentIdx = (idx) => {
    return Math.floor((idx - 1) / 2);
  }
  const getLeftChildIdx = (idx) => {
    return idx * 2 + 1;
  }
  const insert = (value) => { //heap에 값 넣기
    let idx = heap.length;
    heap.push(value);

    let pIdx = getParentIdx(idx);
    while (pIdx >= 0 && value > heap[pIdx]) {
      swap(idx, pIdx, heap);
      idx = pIdx;
      pIdx = getParentIdx(idx);
    }
    return heap;
  }
  const removeRoot = () => { //최대값 제거
    swap(0, heap.length - 1, heap);
    heap.pop();

    if (heap.length === 0) return [];
    let idx;
    let maxIdx = 0;
    while (idx !== maxIdx) {
      idx = maxIdx;
      let left = getLeftChildIdx(idx);
      let right = left + 1;

      if (left < heap.length && heap[left] > heap[maxIdx]) maxIdx = left;
      if (right < heap.length && heap[right] > heap[maxIdx]) maxIdx = right;

      swap(idx, maxIdx, heap);
    }
    return heap;
  }

  works.forEach((value) => insert(value)); //works배열을 최대 힙으로 만든다.
  for (let i = 0; i < n; i++) { //n번 돌면서
    const newValue = heap[0] - 1; //최대 값 -1 값을 변수에 저장
    removeRoot(); //최대 값 제거
    insert(newValue); //최대 값 -1을 새롭게 추가
  }

  return heap.reduce((acc, cur) => acc + cur ** 2, 0);
}

  최대 힙을 사용하면 매번 최대 값을 갱신할 때 works.length보다 더 적은 횟수로 새로운 최대 값을 찾을 수 있다.

 

function solution(n, works) {
  if (works.reduce((a, b) => a + b) <= n) return 0;
  let sorted = works.sort((a, b) => a - b); //오름차순 정렬한다.
  const len = works.length;

  while (n) {
    const max = sorted[len - 1]; //가장 마지막 요소를 가져온다.
    for (let i = len - 1; i >= 0; i--) {
      if(sorted[i] < max){ break; }
      else { //마지막 요소보다 크거나 같은 수들을 모두 똑같이 만든다.
        sorted[i]--;
        n--;
      }
      if (n === 0) break;
    }
  }

  return sorted.reduce((acc, cur) => acc + cur ** 2, 0);
}

  또 다른 방법으로는 처음부터 배열을 정렬하는 방법이 있다. 처음에 배열을 정렬하면 당연히 마지막 요소가 최대 값이다. 마지막 요소이자 최대 값을 -1하면 새로운 최대 값을 찾아야 한다. 그런데 배열이 오름차순 정렬되어있기 때문에 다음 최대 값은 방금 -1한 값 마지막 요소 바로 앞에 있는 값이다. 

 

  works 배열이 [2, 15, 22, 55, 55]와 같이 같은 요소가 중복된다면 마지막 요소에 -1연산을 하면 마지막 요소가 아닌 3번째 요소가 최대 값이 된다. while문 안에서 배열의 마지막 요소가 항상 최대 값임을 보장하기 위해 나머지 요소들 중에서 max와 같거나 큰 값인 경우도 함께 제거한다. 즉, 한 번에 while 문에서 [2, 15, 22, 54, 54]가 된 것이다.