[ 프로그래머스_ Lv3 ] 야근 지수 ( 그리디 - 자바스크립트 )

문제

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

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

 

문제에 대한 이해

 

남은 일을 나타내는 [work] 배열과 끝낼 수 있는 일의 양인 n이 주어진다. 

1시간에 1개의 일을 끝낼 수 있다고 가정 할 때, 야근 지수를 가장 낮출 수 있는 프로그램을 만들어라.

 

풀이 방법

 

[1] 기본적인 방법

 

문제를 봤을 때, 처음에는 오름차순 또는 내림차순으로 정렬하고 1씩 빼주면 되지 않을까? 라는 생각을 가지게 되었다. 

하지만, 몇 번 시뮬레이션을 돌려 봤을 때 "야근 지수"는 일의 양의 제곱근 이기 때문에 가능하다면 큰 수를 우선적으로 줄이는 것을 목표로 해야 한다는 사실을 알게 되었다.

 

즉, 다음 인덱스에 위치한 일을 감소 시키기 위해서는 이전 인덱스에 위치한 일을 다음 인덱스와는 최소한 같게 만들어야 한다.

 

 

[2] 구현

 

[2-1] 투포인터

 

결과적으로는 가장 큰 값과, 2번째로 큰 값을 비교하면서 넘어간다는 생각을 가지게 되었다. 마땅한 방법이 떠오르지 않아서 투포인터를 통해 구현을 하였는데, 로직은 다음과 같다.

 

let left = 0;
let right = 1;

while ( n > 0 )  {
	
	while ( works[left] >= works[right] ) {
    	n -= 1;
        works[left] -= 1;
    }	

	left -= 1;
    right -= 1;
    
    left === -1 ? left = 0 : left;
    right === - 1 ? right = 0 : right;
}

내림차순을 기준으로 정렬한 배열에서 자신보다 뒤에 있는 인덱스 값보다 클 때는, n의 값과 현재 인덱스의 값을 빼주는 방식 이였다.

하지만, 보는 것처럼 while 루프를 2번 돌리면서 탐색을 했기 때문에 "시간복잡도"가 굉장히 엉망이였다.

 

[2-2] 단순 구현

 

문뜩 든 생각은 while 루프가 바깥에서 돌고 있는데 "굳이 내부에서 또 돌려 줘야 하는가?" 라는 생각을 가지게 되었다.

슬라이딩 윈도우는 left 좌표를 고정 해두고 right 좌표를 이동한다고는 하지만 "야근 지수"는 다음의 값과 비교만을 하면 되기 때문에 그러지 않아도 된다는 결론에 도달하였다.

 

그리하여, 내부에 작동하는 로직에서는 

 

1) 다음 인덱스의 값과 비교

2) 끝에 도달 했을 때, 다시 첫 인덱스로 보내주는 것

 

이 두가지 만 구현 하면 됬다.

 

뭐 사실 말로 하면 쉽지만, "투포인터"가 머리에 너무 선명하게 남아 있어서 그런지 idx를 0으로 보내주면 된다는 생각보다는 "일정 길이를 초과하면 나눠서 제자리로 보낸다" 라는 생각이 강해서 시간을 많이 잡아 먹었고 결국에는 구글링을 하게 되었다.

 

 

아래의 코드를 보면 궁극적으로 나와 로직은 같지만 반복적으로 처리했던 로직을 깔끔하게 분리를 한 사례를 찾을 수 있었다.

그 중에서도 아래의 코드를 구현해서 별도의 연산을 없앤 것이 정말 대단하다고 느꼈다.

    if (works[idx - 1] === works[idx]) {
      idx = 0;
      continue;
    }

 

 

전체코드는 다음과 같다.

function solution(n, works) {
  works.sort((a, b) => b - a);

  let idx = 0;

  while (n > 0) {
    if (works[idx] < works[idx + 1]) {
      idx += 1;
      continue;
    }

    if (works[idx - 1] === works[idx]) {
      idx = 0;
      continue;
    }

    works[idx] -= 1;
    n -= 1;
  }

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

 

느낀점



이 문제를 풀면서 느낀거지만, 나는 아직 연산을 줄이는 방법을 잘 모르는 것 같다. 

알고리즘을 많이 풀어서 기본적으로 "어떻게 구현 할지?" 에 대한 방향은 비교적 빠르게 찾는 반면에 이를 효과적으로 구현하는 능력이 아직 부족하다고 여겨진다.

 

이러한 단점은 실질적으로 "시뮬레이션" 문제를 풀거나 "구현'문제를 풀 때 시간 복잡도를 늘리는 것과 깊은 연관성이 있는데 어떻게 하면 연산을 줄이고 더 효과적으로 접근이 가능할지에 대해서 더 고민 하는 습관을 가져야겠다.