Programmers. 쿠키구입

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 쿠키구입

유사한 그리디 문제를 본 적이 있으나 이 문제는 적절히 배열을 두 부분집합으로 나누어 부분집합의 합이 같고 그 값이 최대가 되는 값을 찾아야 한다. 쿠키의 길이가 2000인 것으로 보아 $n^2$ 풀이까지는 가능하겠고 투포인터를 사용하면 해결할 수 있겠다.

• 우측 집합도 원소를 가져야 하므로 쿠키길이 - 2까지만 순회, 좌측 포인터는 현재 값, 우측 포인터는 좌측 포인터 + 1로 설정
• 좌측 집합의 값이 작으면 포인터를 좌측으로 이동, 우측 포인터가 작으면 우측으로 이동해야 한다.
• 이동하면서 좌, 우측 집합의 값이 같으면 정답을 갱신하고 좌, 우측을 1씩 이동시킨다.
• 좌측 포인터를 0부터 N -2지점까지 순회했기에 순회가 끝나면 모든 경우의 수가 반영된다.

python 코드

def solution(cookie):
    if len(cookie) == 1:
        return 0
    N = len(cookie)
    answer = 0
    for i in range(N + 1):
        l, r = i, i + 1
        l_c, r_c = cookie[l], cookie[r]
        while l > -1 and r < N:
            if l_c < r_c and l > 0:
                l -= 1
                l_c += cookie[l]
            elif l_c > r_c and r < N - 1:
                r += 1
                r_c += cookie[r]
            elif l_c == r_c:
                if l > 0 and r < N - 1:
                    answer = max(answer, l_c)
                    l -= 1
                    r += 1
                    l_c += cookie[l]
                    r_c += cookie[r]
                else:
                    break
            else:
                break
    return answer