[Algorithm] 프로그래머스 - 쿠키 구입

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

접근

N개의 바구니에 과자 수가 차례대로 들은 배열 cookie가 입력으로 주어진다.

문제에서 요구하는 바는 l ~ m 바구니의 과자 수의 합과 m+1 ~ r 바구니의 과자 수의 합이 같으면서 그 합이 최대로 되는 값이다.

제한사항을 확인해보면, cookie의 길이는 1 이상 2,000 이하이기 때문에 이중 for문까지는 괜찮아 보인다.

따라서, $O(n^2)$의 성능을 보이는 알고리즘을 택해서 문제를 풀어보겠다.

(l부터 m까지의 합) = (m+1부터 r까지의 합) 에서 1부터 n까지의 합을 정의하는 배열 d를 대입해보자.

$d[m] - d[l-1] = d[r] - d[m]$

$2 * d[m] = d[r] + d[l-1]$

이 방정식을 풀면 된다. 변수가 세 개이지만, 이중 for문으로 해결할 수 있다.

m이 l 이상이며, r 이하인 조건을 활용하면 된다.

l부터 r까지의 iteration에서 증가하는 값을 Set에 넣어 $d[r] + d[l-1]$이 포함되어 있는지 검사한다.

소스코드(Java)

import java.util.*;

class Solution {
    public int solution(int[] cookie) {
        int[] d = new int[cookie.length+1];

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

        int result = 0;
        int max = 0;

        for(int l = 1; l < cookie.length; l++) {
            Set<Integer> mSet = new HashSet<>();
            for(int r = l; r <= cookie.length; r++) {
                mSet.add(2*d[r]);
                max = (d[r]+d[l-1])/2-d[l-1];
                if((d[r]+d[l-1]) % 2 == 0 && mSet.contains(d[r]+d[l-1]) && result < max) {
                    result = max;
                }
            }
        }

        return result;
    }
}

효율성 테스트 실패

주어진 제한사항은 준수했지만, 효율성 테스트에서 시간 초과가 나왔다.

보통 이런 건 문제에서 효율성 테스트 제한사항도 주지 않나? 흠…

다시 접근

왜,,, 시간 초과가 나왔을까 생각해보자. 아무리 생각해도 이 문제를 $O(n^2)$ 보다 낮게 풀 수 있을 거라는 생각이 들지 않는다.

저 시간 초과라는 것도 큰 차이가 아닌 작은 차이로 나온 결과일 수도 있다. 그럼 간소한 차이로 내 시간을 갉아먹는 녀석은 누구인가.

아무래도 의심가는 녀석은 HashSet 밖에 없다. HashSet의 성능에는 initialCapacity와 loadfactor가 크게 작용한다.

삽입 시 평균 시간 복잡도는 $O(1)$이지만, 버킷이 하나밖에 존재하지 않는 최악의 경우에는 $O(n)$이 된다.

JDK 8 부터는 최악의 경우 시간 복잡도가 $O(logn)$이라고 한다.

같은 hashcode 값을 가진 객체를 하나의 버킷에 저장할 때 일정 수까지는 링크드 리스트를 이용하지만, 그 후에는 트리 형태로 저장한다는 거 같다.

• initialCapacity
  • 낮게 설정 → 공간 복잡도 낮아져, iteration에 시간이 적게 걸림. 그만큼 rehashing(높은 비용)이 많이 일어남.
  • 높게 설정 → iteration에 시간이 많이 걸리고, 초기 메모리 낭비 높아짐.
  • 적절하게 설정하는 것이 중요
• loadfactor
  • size = capacity * loadfactor
  • initialCapacity와 마찬가지로, 용량에 영향을 주는 요소
  • 적절하게 설정하는 것이 중요

난 그냥 공간 복잡도를 손해보기로 했다. 풀이는 간단하다.

참고로, 용량을 5,000,001로 잡은 건 요구조건을 충족하는 쿠키를 다 더한다 한들, 10,000,000을 넘지 못할 것이고, 이를 반으로 나눈 게 문제에서 요구하는 바이기 때문이다.

소스코드(Java)

import java.util.*;

class Solution {
    public int solution(int[] cookie) {
        int[] d = new int[cookie.length+1];

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

        int max = 0;

        boolean[] arr = new boolean[5000001];

        for(int l = 1; l < cookie.length; l++) {
            for(int r = l; r <= cookie.length; r++) {
                arr[2*d[r]] = true;
                if((d[r]+d[l-1]) % 2 == 0 && arr[d[r]+d[l-1]] && max < (d[r]+d[l-1])/2-d[l-1]) {
                    max = (d[r]+d[l-1])/2-d[l-1];
                }
            }
        }

        return max;
    }
}

효율성 테스트 성공

이런 애매한 걸로 괴롭히면 너무 힘들다…

다른 접근

보니까 투 포인터 알고리즘을 사용해서 풀기도 하던데 이것도 알아두면 좋은 거 같다.

투 포인터 알고리즘(Two Pointer Algorithm)은 배열이나 링크드 리스트와 같은 선형 데이터 구조에서 효과적으로 사용되는 알고리즘이다. 이 알고리즘은 두 개의 포인터를 사용하여 문제를 해결하는 방식이다.

• 일반적인 동작
  • 배열이나 리스트의 양 끝에서 시작하는 두 개의 포인터 사용
  • 각 포인터를 특정 조건에 따라 서로 다른 방향으로 이동
  • 두 포인터가 특정 조건을 만족할 때까지 이 과정을 반복
• 활용
  • 배열에서 두 수의 합이 특정 값이 되는 쌍을 찾기
  • 배열에서 가장 긴 부분 수열 찾기
  • 문자열에서 회문(palindrome) 찾기
  • 배열에서 중복된 원소 제거하기
  • 배열에서 특정 부분합을 가지는 부분 배열 찾기

투 포인터 알고리즘은 $O(n)$, 선형 시간 복잡도를 가지며, 추가적인 공간 복잡도가 필요하지 않아 효율적이다.

하지만, 이 문제의 경우 각 인덱스마다 투 포인터 알고리즘을 수행해야 하므로, 최악의 경우 시간 복잡도 $O(n^2)$을 가진다. 근데 내 거보다 확실히 빠르긴 하다.

이 문제는 cookie 배열에서 가장 큰 쿠키 크기를 찾는 문제이다. 여기서 쿠키란 왼쪽과 오른쪽 부분합이 같은 부분 배열을 의미한다.

1. left와 right 포인터를 이용하여 배열의 양쪽 끝에서 중간으로 이동하며 탐색한다.
2. leftSum과 rightSum을 계산하여 두 합이 같은지 확인한다.
3. 두 합이 같다면 현재 "쿠키" 크기를 저장하고, maxCookie 변수에 최대값을 업데이트한다.
4. leftSum이 rightSum보다 크다면 right를 오른쪽으로 이동시켜 rightSum을 증가시킨다.
5. leftSum이 rightSum보다 작다면 left를 왼쪽으로 이동시켜 leftSum을 증가시킨다.
6. 이 과정을 left와 right가 교차할 때까지 반복한다.
7. 최종적으로 maxCookie 변수에 저장된 값을 반환한다.

소스코드(Java)

class Solution {
    public int solution(int[] cookie) {
        int n = cookie.length;
        int maxCookie = 0;

        for (int i = 0; i < n - 1; i++) {
            int left = i, right = i + 1;
            int leftSum = cookie[i], rightSum = cookie[i + 1];

            while (left >= 0 && right < n) {
                if (leftSum == rightSum && leftSum > maxCookie) {
                    maxCookie = leftSum;
                }

                if (leftSum <= rightSum) {
                    left--;
                    if (left >= 0) {
                        leftSum += cookie[left];
                    }
                } else {
                    right++;
                    if (right < n) {
                        rightSum += cookie[right];
                    }
                }
            }
        }

        return maxCookie;
    }
}