Summer/Winter Coding - # 12. 쿠키 구입
코딩 테스트 연습 - 쿠키 구입 | 프로그래머스 스쿨 (programmers.co.kr)
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
12. 쿠키 구입
과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 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 이하인 자연수입니다.
입출력 예cookieresult
| [1,1,2,3] | 3 |
| [1,2,4,5] | 0 |
입출력 예 #1
첫째 아들에게 2, 3번 바구니를, 둘째 아들에게 4번 바구니를 사주면 두 아들은 각각 과자 3개를 받습니다.
입출력 예 #2
주어진 조건에 맞게 과자를 살 방법이 없습니다.
[문제 해설]
0. 쿠키의 개수를 같게 주는 조건을 전제로 최대로 줄 수 있는 값을 리턴하는 문제입니다.
1. 이문제의 어려움은 단순하게 인덱스를 이어나가면서 단순히 쿠키의 최댓값을 찾는 거에서 각 형제의 쿠키의 수가 같아야 하는 조건이 문제 어려움 입니다.
2. 그렇기에 조건을 맞추면서 몇 번째 인덱스를 시작으로 쿠키를 나누어야 최대가 될지..
즉, 시작은 몇 번째로 시작하고 몇 번째 인덱스 기점으로 첫째와 둘째를 나눠서 쿠키를 줄지가 그리디하게 풀기가 어렵습니다.
3. 이렇게 그리디하게 풀지 못할 거 같을 때는 완전 탐색은 좋은 방법입니다.
4. 언제부터 스타트를 해야할지 판단하기 어렵습니다 => 때문에 0 ~ length - 1까지 for 문을 돌릴 겁니다.
5. 쿠키의 개수를 같게 하면 최댓값을 만들기가 어렵습니다 => 4번에서의 for문의 idx를 기준으로 탐색을 구현합니다.
6. 첫 시작은 idx, idx + 1로 시작합니다.
7. 순회하면서 첫째의 쿠키의 개수보다 둘째가 많다면 첫째의 idx 위치를 - 1을 해줍니다. 그러고는 idx - 1 위치의 쿠키를 더해줍니다. 결론적으로 첫째는 idx - 1, idx의 쿠키를 가지는 상태가 되고, 둘째는 idx + 1의 쿠키를 가지는 상태가 됩니다. 이렇게 계속 순회를 돌면서 쿠키가 같아지는 경우를 찾습니다.
7 - 1. 반대로 첫째 > 둘재라면, idx, idx + 1 상태에서 둘째를 idx + 1 + 1을 해줘서 둘째는 idx + 1, idx + 2 위치를 쿠기를 가지게 해주는 방식으로 순회하는 것.
단, idx가 0보다 작아지거나 length 보다 커질 경우 그 즉시 순회를 종료하고 5번의 단계로 돌아 가서 다음 순회를 시작합니다.
8. 쿠키의 수가 같아지는 경우 answer = max(answer, 쿠키의 수)를 최신화해줍니다.
다시 이어가서 각각 첫째 idx - 1을 더해주고, 둘째 idx + 1을 해줘서 다시 5번의 순회를 시작합니다. 마찬가지로 리스트의 크기를 초과하면 5번의 순회는 종료됩니다.
9. 4번의 idx가 length - 1이 될 때까지 탐색을 완료하고 answer을 리턴하면 됩니다.
[코드]
def solution(cookie):
answer = 0
for idx in range(len(cookie) - 1):
start, end = idx, idx + 1
first, second = cookie[start], cookie[end]
while True:
if first < second:
start -= 1
if start < 0:
break
first += cookie[start]
elif first > second:
end += 1
if end >= len(cookie):
break
second += cookie[end]
else:
answer = max(answer, first)
end += 1
start -= 1
if end >= len(cookie) or start < 0:
break
second += cookie[end]
first += cookie[start]
return answer
후기
그리디 하게 못 풀겠으면 완전 탐색을 생각해본다.
완전탐색을 떠올린다 해도 풀긴 어렵습니다.
하지만 그런 생각도 못하게 된다면 시작조차 못합니다.
이 문제를 시작으로 시작을 시작할 수 있게 해주는 문제 같습니다.