문제

풀이 과정

구현 문제. 정답을 찾는 건 쉽지만, 효율성 테스트가 있다.
이 효율성 테스트를 통과하는 게 어려웠는데, 문제 풀이 과정에서 단순히 sort() 쓰면 시간 초과가 일어나게 끔 했다. 대강 시간 복잡도를 O(N) 으로 끝낼 수 있는 정렬을 만들어야 문제가 해결되는 듯 하다.

해당 문제의 풀이과정은 다음과 같다.

1. 일단 정렬 (더해지는 제곱 값은, 값이 큰 걸 작게 만들어주는 것이 더했을 때 가장 작게 나온다)
2. 가장 큰 값을 n번 만큼 감소시킨다. 감소 시킬 경우 배열의 Max 가 변할 수 있으니 주의한다.
3. 계속 줄이다 보면 음수가 나올 수 있다. 음수도 제곱하면 값이 생기기 때문에, 주의하자
   나의 경우에는 어차피 내림차순 정렬을 해둔 상태이니 arr[0] 이 0이라면 더이상 볼 필요 없으므로 감소하는 걸 끝내버렸다.
4. 다 줄였으면 제곱해서 더해서 값 구하자.

이것만으로 정답은 대강 맞을 것이다.
문제는 효율성인데, 나의 경우는 arr[0] 하고 arr[1] 만 봤다.

효율성 테스트 통과하기

1. 내림 차순이니 arr[0] 이 가장 큰 값일텐데 n 번 만큼 줄이다 보면 arr[1] 이 더 커지는 상황이 나올거다.

2. arr[0] 이 arr[1] 보다 작다면 그냥 두 수를 swap 해준다. 단, 주의할 점이 2가지 있다.
   2-1. arr[1] 이 더 크긴 하지만 arr[2], arr[3], … 도 arr[1] 과 동일한 값을 가지고 있어, arr[0] 이 더 뒤로 밀려놔야 하는 상황 → idx=2 부터 시작하여, arr[0] 과 동일하거나 작은 값이 나오는 경우, 그거보다 한단계 앞의 idx 와 바꿔주자. (그게 arr[0] 보다 내림차순 배열에서 마지막으로 큰 값이다)
   2-2. arr[0] 배열의 맨 뒤로 가야하는 경우, 즉 가장 작은 값이 되버리는 경우이다. idx 가 만약 배열의 length 까지 도달할 때 까지 반복문이 끝나지 않았다면 해당 상황이라고 판단하여, 맨 앞의 값을 배열의 뒤로 넣어줬다.

3. 번외로 이분탐색 써서 교체할 idx 를 찾았어도 이론상 됬을거 같다! (요런 건 꼭 풀고 나서야 생각남)

우큐가 떠올라서, 직접 구현할까 하다가 한번도 그런걸 안해봐서 포기했다. 해당 풀이를 위한 클래스나 메서드를 직접 생성하여 문제를 푼 코드를 몇번 본 적 있는데, 그런 것도 할 수 있으면 되게 좋을 거 같다는 생각이 든다.

정답

function solution(n, works) {
  works.sort((a,b)=> b-a);
  while(--n>=0) {
    if(works[0] == 0) break;
    works[0]--;
    if(works[0] < works[1]) {
      let idx = 2;
	  while(true) {
        if(works[idx] <= works[0]) {
          let tmp = works[idx-1];
          works[idx-1] = works[0];
          works[0] = tmp;
          break;
        } else if(idx == works.length) {
          works.push(works.shift());
          break;
        } 
        idx++;
      }
    };
  }
  let ans = 0;
  for(let num of works) ans += (num*num);
  return ans;
}