[프로그래머스] 쿠키 구입 (Python)

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

프로그래머스

 

Status : Solved

 

Time : 00:13:28

 

---

 

문제 설명

 

과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 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

 

 

---

 

풀이

 

이게 Level 4라고...? 문제.

 

m을 기준으로, l=m, r=m+1로 두고 투 포인터 탐색을 진행하는 게 포인트다. 모든 m에 대해서 수행하면 된다.

• 만약 현재 좌측 누적합과 우측 누적합이 같다면 두 포인터를 좌우로 옮긴다.
• 좌측 누적합이 크다면 우측 포인터를 오른쪽으로 옮긴다.
• 우측 누적합이 크다면 좌측 포인터를 왼쪽으로 옮긴다.
• 두 누적합을 업데이트한다. 포인터 위치가 변경되었다면 포인터가 가리키는 리스트값을 누적합에 더해주면 된다. 만약 범위를 벗어나 업데이트를 불가능하다면 반복을 종료한다.

 

이런 식으로 탐색을 진행하면 m 탐색에 O(N), 투 포인터 탐색에 O(N)이 소요되므로 총 O(N^2)의 시간복잡도를 가지게 된다. N < 2000이므로 충분히 해결 가능한 시간복잡도이다. 아니면 애초에 누적합을 구해놓고 진행해도 크게 무리는 없을 듯 싶다.

 

 

풀이 코드

def solution(cookie):
    N = len(cookie)
    answer = 0
    
    check_l = lambda l : cookie[l] if -1 < l else 0
    check_r = lambda r : cookie[r] if r < N else 0
    
    for m in range(N-1) :
        l, r = m, m+1
        lsum, rsum = cookie[l], cookie[r]
        while -1 < l < r < N :
            if lsum == rsum :
                answer = max(answer, lsum)
                l -= 1
                r += 1
                lsum += check_l(l)
                rsum += check_r(r)
                    
            elif lsum > rsum :
                r += 1
                rsum += check_r(r)
            else :
                l -= 1
                lsum += check_l(l)
            
    return answer

풀이 완료~