문제 설명 및 제한사항
문제 설명
과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 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 이하인 자연수입니다.
아이디어 및 해결 방법
배열 내의 특정 구간의 합을 빠르게 구해야 하므로, 누적합 배열을 쓰면 좋을 것 같다는 아이디어를 떠올립니다.
문제 조건 A[l]+...+A[m] == A[m+1]+...+A[r]을 누적합 배열 C 상의 관계로 표현하면 어떻게 될까요?
이는 곧 C[m] - C[l-1] == C[r] - C[m] 이므로, 결국 C[m] = (C[r] + C[l-1]) / 2 의 관계식을 얻을 수 있게 됩니다.
누적합 배열 C 내의 모든 인덱스 쌍 (l, r)에 대해서 C[l] ~ C[r] 사이에 (C[l-1] + C[r]) / 2 값을 가지는 C[m] (l <= m <= r) 이 존재하는지 확인합니다. 이 값이 존재하면 A[l] + ... + A[m] == A[m+1] + ... + A[r] 이라는 의미이므로, C[m] - C[l-1] 값을 답의 후보로 저장한 뒤, 마지막에 그 중 가장 큰 값을 답으로 냅니다.
탐색은 l, r에 대한 이중 for 문으로 해결하되, r을 늘려갈 때, l~r 사이에 있는 모든 C[m]값을 set에 저장해두고 존재 유무를 O(1)에 판단할 수 있게 효율화합니다.
코드
def solution(cookie):
# 누적합 배열 C 내의 모든 인덱스 쌍 (l, r)에 대해서
# C[l] ~ C[r] 사이에 (C[l-1] + C[r]) / 2 값을 가지는
# C[m] (l <= m <= r) 이 존재하는지 확인합니다.
# 존재하면 A[l] + ... + A[m] == A[m+1] + ... + A[r]
# 이라는 의미이므로, C[m] - C[l-1] 값을 저장합니다.
#
# 탐색은 l, r에 대한 이중 for 문으로 해결하되,
# r을 늘려갈 때, l~r 사이에 있는 모든 C[m]값을 set에 저장해두는
# 식으로 효율화합니다.
C = [0, cookie[0]]
for c in cookie[1:]:
C.append(C[-1] + c)
answers = []
for l in range(1, len(cookie)):
mids = {C[l]}
for r in range(l+1, len(cookie) + 1):
target = (C[l-1] + C[r]) / 2
if target in mids:
answers.append(target - C[l-1])
mids.add(C[r])
return int(max(answers)) if answers else 0
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges