[Summer/Winter Coding(~2018)][누적합] 쿠키 구입 - Java

문제 바로가기

프로그래머스

 

프로그래머스 레벨4짜리 문제입니다.

효율성도 있어서 짜증나는 문제인데요, 레벨 4 정도는 아닌듯...?????????

 

public int solution(int[] cookie) {
    int answer = 0;

    // 누적합
    int[] sum = new int[cookie.length + 1];

    sum[0] = 0;
    sum[1] = cookie[0];

    for (int i = 2; i <= cookie.length; i++) {
      sum[i] += sum[i - 1] + cookie[i - 1];
    }

    for (int i = 1; i < cookie.length; i++) {
      answer = Math.max(answer, check(i, sum));
    }

    return answer;
  }

  public int check(int idx, int[] sum) {
    int left = 0;
    int right = sum.length - 1;

    while (left < right) {
      int leftSum = sum[idx] - sum[left];
      int rightSum = sum[right] - sum[idx];

      if (leftSum == rightSum) {
        return leftSum;
      } else if (leftSum > rightSum) {
        left++;
      } else {
        right--;
      }
    }

    return 0;
  }

 

기본적인 아이디어는 누적합을 이용하는 겁니다.

cookie = [1, 1, 2, 3] 인 경우 누적합 배열 S[i]는 [1, 2, 4, 7] 이 되겠죠. 여기에 계산상 편의를 위해 맨 앞에 0을 꽂아줬습니다.

 

누적합 배열을 갖고 이제 답을 찾아보면 됩니다.

S[r] - S[m] 은 m번 바구니 ~ r번 바구니에 든 사과의 개수가 됩니다.

 

여기서!!! 효율성에 걸린 첫번째 코드를 한 번 보겠습니다.

 

public int checkV1(int idx, int[] sum) {
    Set<Integer> first = new LinkedHashSet<>();
    Set<Integer> second = new LinkedHashSet<>();

    for (int i = 0; i < idx; i++) {
      first.add(sum[idx] - sum[i]);
    }

    for (int i = sum.length - 1; i >= idx + 1; i--) {
      second.add(sum[i] - sum[idx]);
    }

    for (int n : first) {
      if (second.contains(n)) {
        return n;
      }
    }

    return 0;
  }

 

각각의 Set에 첫째와 둘째의 사과 개수를 저장해두고, 동일한 원소가 들어있으면 걔를 리턴하도록 했습니다. 이때 가장 큰 값을 리턴해주어야 하므로 입력 순서가 보장되는 LinkedHashSet을 이용하고, 먼곳(사과 개수가 큰)에서 부터 Set에 원소를 추가했습니다.

 

정렬이 되는 TreeSet을 써도 되겠지만, TreeSet은 오름차순으로 정렬되기 때문에 descendingSet() 을 한 번 해주어야 하기 때문에 효율성 장담 못합니다~

 

근데 Set을 사용하니깐 효율성에서 다 틀립니다. 가장 큰 경우 하나만 찾아서 리턴하면 되는데, 모든 경우를 다 저장해서 그런가봅니다.

 

 

그래서 다시 정답 코드로 돌아가면..

 

간단합니다. 기준점이 되는 idx에서 각각 왼쪽/오른쪽 끝에서부터 사과 개수를 구해주는 겁니다.

굳이굳이 따지자면 투 포인터 느낌이 납니다. 

 

이렇게 하면 우리가 원하는 사과 개수의 최댓값을 구하자마자 바로 반환해주기 때문에 효율성에 통과할 수 있답니다 ~~ ^^^^

 

레벨 4 우우~~~