문제를 읽어보면 두개의 큐가 같은 합을 가져아한다고 말한다.
이 때 두개의 큐의 합의 절반을 각각의 큐가 가져야 한다는 것을 알 수 있다.
두개의 큐의 합의 절반을 가진 큐를 구하기 위해
두개의 큐가 하나로 합쳐져 있다고 생각하면 구간 합이라는 것을 알 수 있다.
생각해야 할 점은 구간합이 두개의 큐의 합의 절반이더라도 또 다른 구간이 나올 수 있으므로
구간합이 두개의 큐의 합의 절반이더라도 탐색을 종료하면 안된다.
또 생각해야 할 점은 구간이 정해졌을 때 end가 큐의 길이보다 작을 때와 클 때의 작업 횟수가 다르다는 점이다.
def solution(queue1, queue2):
s = (sum(queue1)+sum(queue2))/2
start , end = 0, 0
q = queue1+ queue2
_s = 0
ans = 1e9
while True:
if _s >s:
_s -= q[start]
start +=1
elif _s == s:
if end - len(queue1)>=0:
ans=min(ans, start+end-len(queue1))
else:
ans=min(ans,start+2*len(queue1)-end)
_s -= q[start]
start +=1
elif end == len(queue1)*2:
break
else:
_s += q[end]
end+=1
if ans == 1e9:
return -1
else:
return ans
제 풀이가 정답을 맞긴 했지만
q = queue2 + queue1
으로 바꾸면 테스트 1번만 실패하게 됩니다.
제 생각엔 start, end 의 위치에 따른 작업 횟수가 다른 점에서 놓친거 같습니다.
이와 관련해서 답을 아시는 분 계시면 댓글로 적어주시기 바랍니다.
'문제풀이 > 프로그래머스' 카테고리의 다른 글
[프로그래머스 문제풀이]2023 KAKAO BLIND RECRUITMENT 표현 가능한 이진트리 (0) | 2023.02.28 |
---|---|
[프로그래머스 문제풀이] 코딩 테스트 준비 (1) | 2022.08.23 |
[프로그래머스 문제풀이] 성격 유형 검사하기 문제풀이 (0) | 2022.08.23 |
[프로그래머스 문제풀이] 양과늑대 문제풀이 (0) | 2022.08.16 |
[프로그래머스 문제풀이] 배달 문제풀이 (0) | 2021.09.06 |