[프로그래머스] LV.4 쿠키 구입 (JS)

문제

과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 1번부터 N번까지 차례로 번호가 붙은 바구니 N개를 일렬로 나열해 놨습니다.

철수는 두 아들에게 줄 과자를 사려합니다. 첫째 아들에게는 l번 바구니부터 m번 바구니까지, 둘째 아들에게는 m+1번 바구니부터 r번 바구니까지를 주려합니다. 단, 두 아들이 받을 과자 수는 같아야 합니다(1 <= l <= m, m+1 <= r <= N). 즉, A[i] 를 i번 바구니에 들어있는 과자 수라고 했을 때, A[l]+..+A[m] = A[m+1]+..+A[r] 를 만족해야 합니다.

각 바구니 안에 들은 과자 수가 차례로 들은 배열 cookie가 주어질 때, 조건에 맞게 과자를 살 경우 한 명의 아들에게 줄 수 있는 가장 많은 과자 수를 return 하는 solution 함수를 완성해주세요. (단, 조건에 맞게 과자를 구매할 수 없다면 0을 return 합니다)

제한

• cookie의 길이는 1 이상 2,000 이하입니다.
• cookie의 각각의 원소는 1 이상 500 이하인 자연수입니다.
  
  

입출력 예시

cookie	result
[1,1,2,3]	3
[1,2,4,5]	0

풀이

2018 Summer/Winter Coding 테스트에서 출제된 문제이다. 주어진 cookie의 길이가 최대 2000 이기 때문에 시간 제한이 그렇게 빡빡하지 않을 것 같다는 생각이 든다. 최대값이 2000 정도이면 O(n^2)의 시간복잡도도 크게 문제가 되지 않을 것 같다. 따라서 이를 염두해두고 문제를 풀어보자.

1) 기준점

두 구간의 합이 일치하는 경우는 없을 수도 있고, 딱 1개만 존재할 수도 있으며 여러 개가 존재하는 경우가 있을 수도 있다. 이를 특정할 수 없기 때문에 사실상 주어진 cookie에서 모든 구간을 검사해보아야 한다.

그러나 모든 구간을 검사하는 경우의 수는 매우 크다. 시작범위와 종료범위는 모두 배열의 시작 인덱스부터 마지막 인덱스까지 가능하기 때문이다. 각각의 범위는 일정한 방향으로 증가하는 것이 아니기 때문에 범위가 주어졌을때 고려해야하는 경우의 수가 매우 많아진다. 예를 들어 1 - 4개의 쿠키 바구니가 있다고 했을 시 다음의 경우의 수가 존재한다.

• 1 - 2
• 1 - 2, 3
• 1 - 2, 3, 4
• 1, 2 - 3
• 1, 2 - 3, 4
• 1, 2, 3 - 4
• 2 - 3
• 2 - 3, 4
• 2, 3 - 4
• 3 - 4

이는 cookie에 담긴 값이 일정하지 않은 바구니 속 쿠키의 개수이기 때문에, 모든 요소에 일일이 접근하여 확인하는 과정이 필요하기 때문이다. 제한시간이 널널한 편이지만 이 같은 방식으로 접근한다면 당연히 시간초과에 걸릴 것이다.

하지만 우리는 위와 같은 방식에서 다음의 의문점을 생각할 수 있다.

• 범위를 늘려가다/줄여가다 두 범위의 합이 일치하지 않는 순간에서는 중단하면 되지 않을까?

다음과 같은 의문이 떠올랐다면 매우 훌륭하다. 우리는 이 의문점을 적극적으로 도입하여 문제를 해결할 것이기 때문이다.

문제를 살펴보면 첫째 아들에게 나눠주는 범위는 1 <= l <= m이 되고, 둘째 아들에게 나눠주는 범위는 m+1 <= r <= N이 되는 것을 볼 수 있다. 따라서 첫째 아들의 종료지점보다 1만큼 떨어진 지점이 둘째 아들의 시작지점이 된다는 것을 파악할 수 있다. 이를 그림으로 나타내면 아래와 같다.

따라서 우리는 두 개의 기준점을 설정할 수 있다. 이들은 각각 종료와 시작이기 때문에 범위를 이동하는 방향이 서로 다르다. 때문에 두 개의 기준점을 잡는다면 아래와 같이 범위이동을 하며 해당 범위의 합을 계산할 수 있다.

• left의 종료지점 : 범위 감소 until 0 까지
• right의 시작지점 : 범위 증가 until cookie.length 까지

기준점이 두 개이기 때문에 쉽게 투 포인터 알고리즘을 떠올릴 수 있다. 각각의 기준점을 포인터처럼 활용하여 각 구간의 범위를 조정하며 구간합을 구해주도록 하자. 그리고 이 구간이 일치하는지 확인하며 반복을 진행해주면 될 것이다.

이때 여전히 각 바구니에 들어있는 값은 불규칙적이기 때문에 위와 같은 방식을 모든 cookie에 값에 적용하여야 한다. 따라서 cookie.length만큼 반복문을 돌면서 투 포인터의 크기를 다음과 같이 설정해주자.

let len = cookie.length;
let answer = 0;

// right = i+1 이기 때문에 len-1 범위까지 반복
for(let i = 0; i < len-1; i++) {
  let left = i;	// i는 left의 종료지점
  let right = i + 1;	// i+1은 right의 시작지점
  let lsum = 0;	// left 구간의 합을 저장할 변수
  let rsum = 0;	// right 구간의 합을 저장할 변수
  
  // ... 범위를 조정하는 로직 구현 ...
}

2) 범위 조정

위에서 우리는 left의 종료지점과 right의 시작지점을 cookie의 크기만큼 반복문을 돌면서 설정해주었다. 또한 각 구간의 진행방향이 서로 다르기 때문에 left의 범위는 줄어드는 쪽으로, right의 범위는 늘어나는 쪽으로 진행된다는 것 역시 살펴보았다.

그리고 앞서서 한 가지 의문점에 대해 살펴보았는데, 이 의문점을 적용하여 두 구간의 범위를 조정해주도록 하자. 가장 핵심이 되는 부분은 두 구간의 합이 일치하지 않는 경우를 적절히 판단하여 범위를 조정해야 한다는 점이다.

가장 먼저 파악할 수 있는 조건은 lsum === rsum 이 되는 순간이다. 이때 우리가 리턴해야 할 최종 결과값은 과자수의 최대값이기 때문에 answer < lsum (또는 rsum도 가능)을 동시에 만족해야 한다.

1. 첫번째 조건 : lsum === rsum && answer < lsum

그 외의 경우는 두 구간의 합이 일치하지 않는 경우가 될 것이다. 일치하지 않는 경우는 크게 다음 두 가지로 나누어 생각할 수 있다.

• 반복을 중단하고 다음 기준점으로 넘어갈 것 인가?
• left 또는 right의 범위를 다시 재조정할 것 인가?

반복을 중단하고 다음 기준점으로 넘어가는 경우는 left의 시작지점이 배열의 시작점인 0이 되는 순간이거나 right의 종료지점이 배열의 마지막 지점인 cookie.length - 1이 되는 지점이 되는 순간일 것 이다. 왜냐하면 이 시점에서는 더 이상 구간의 범위를 재조정할 수 없기 때문이다. 즉 각 구간이 한계치에 도달하는 순간이라고 볼 수 있다.

이러한 상황이 아니라면 두 구간의 범위는 계속해서 조정될 수 있다. 따라서 left 구간의 경우는 lsum이 rsum 보다 작으면서 left !== 0인 경우에 다음 범위로 진행 가능하다. 반대로 right 구간의 경우는 rsum이 lsum 보다 작으면서 right !== len-1인 경우에 계속 다음 범위로 진행 가능하다.

이때 한 가지를 주의해야 한다. 위와 같이 범위를 조정하다 보면 중간에 두 값이 일치하는 순간이 나올 수 있다. 그리고 한 번 일치한 이후의 범위에서도 계속해서 일치하는 값이 등장할 수 있다. 그러나 이 값은 항상 이전에 구한 answer 보다 크다는 것을 보장하지 않는다. 말 그대로 바구니 속 쿠키들은 무작위로 배열되어 있기 때문이다. 우리는 이 일치하는 순간을 고려해주어야 제대로 된 정답을 만들 수 있다. 첫 번째 조건에서 기존 answer 보다 큰 결과값은 이미 처리하고 있기 때문에, 나머지 조건문에서는 이미 이보다 작은 경우를 말하고 있다. 따라서 left 또는 right 구간 둘 중 하나에서 두 구간합이 같아지는 순간까지 모두 처리하도록 해주어야 한다. 이는 두 구간 중 어느 한 곳에서라도 수행되면 문제없다. 어차피 범위가 한계지점에 다다르지 않는 이상은 계속해서 재조정 될 것이기 때문이다. 따라서 다음과 같은 조건을 추가로 고려해주자.

2. 두번째 조건 : lsum <= rsum && left !== 0
   • lsum이 rsum 보다 작거나 같아지는 지점까지 모두 고려
   • 세번째 조건에서 수행해도 상관없다.
3. 세번째 조건 : rsum < lsum && right !== len-1
4. 네번째 조건 : else break;

이들 조건을 모두 구현한 무한루프를 앞서 구현한 for 반복문 내부에 구현해주자.

for(let i = 0; i < len-1; i++) {
  ...
  
  // 초기 lsum과 rsum 값 계산
  lsum += cookie[left];
  rsum += cookie[right];
  
  while(true) {
    // 두 구간 합이 같으면서 이전보다 더 큰 값이 경우 갱신
    if (lsum === rsum && answer < lsum) {
      answer = lsum;
    } 
    // lsum이 작다면 (어느 한 곳에서 같은 경우까지 고려)
    else if (lsum <= rsum && left !== 0) {
      // left의 범위를 1줄이고, 해당 위치의 쿠키개수를 누적
      lsum += cookie[--left];
    } 
    // rsum이 작다면
    else if (rsum <= lsum && right !== len-1) {
      // right의 범위를 1늘리고, 해당 위치의 쿠키개수를 누적
      rsum += cookie[++right];
    } 
    // 위 조건에 모두 부합하지 않는 경우라면
    // 둘 중 하나의 구간이 한계치에 도달했다는 것
    else {
      break;
    }
  }
}

return answer;

3) 전체코드

Lv.4에 랭크되어 있는 문제지만 차근 차근 접근하면 생각보다 쉽게 해결할 수 있는 문제라고 생각한다. 두 개의 기준점을 설정하고 이에 대한 누적합을 구하면서 최대값을 구한다라는 생각을 떠올렸다면 큰 어려움 없이 구현할 수 있을듯 하다. 주석을 제외한 전체코드는 다음과 같다.

function solution (cookie) {
  let len = cookie.length;
  let answer = 0;
  
  for(let i = 0; i < len-1; i++) {
    let left = i;
    let right = i+1;
    let lsum = cookie[left];
    let rsum = cookie[right];
    
    while(true) {
      if (lsum === rsum && answer < lsum) {
        answer = lsum;
      } else if (lsum <= rsum && left !== 0) {
        lsum += cookie[--left];
      } else if (rsum <= lsum && right !== len-1) {
        rsum += cookie[++right];
      } else {
        break;
      }
    }
  }
  
  return answer;
}

출처

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