✨[2022KAKAO TECH INTERNSHIP: 두 큐 합 같게 만들기](Python)

문제

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

프로그래머스

유형 

• 투포인터 
• 이분탐색 

알아야 하는 것

• 이분탐색 (Binary Search)
• 문제가 주어지면 가장 단순한 형태로 바꿔보자 

문제풀이 

• 두 큐의 합이 서로 같다는 것은 한 큐의 원소의 합이 전체의 절반이라는 것임 !
  -> 큐 하나에 대해서만 생각하자 
• q = queue1 + queue2 , 새로운 전체 큐에 대해서 0~ len(q)사이의 부분 큐의 합이 전체 합의 절반이 되는 경우가 있는지 살펴보기 
  -> 한 큐에 대해서 살펴보면 된다는 것 ok, 그런데 왜 그 큐의 left, right 인덱스가 0~len(q) 사이에 존재하는 경우만 살펴보면 되는가?
  -> 왜냐하면, left > right 인 경우(== right 인덱스가 범위를 벗어난 경우) 는 이미 0~len(q) 사이의 큐 고려할 때 따진 경우와 동치임  (ex. [2:4]인 큐의 합이 절반과 같은 지 == [left4: right2]큐의 합이 절반과 같은지)
• left idx, right idx 를 따라 전체 리스트에서 합이 절반보다 작으면 right +1, 절반보다 크면 left +1 수행하기 
• 절대 불가능한 경우 return -1  
  -> 전체 합이 홀수인 경우 
  -> 절반인 경우를 못 찾고 left > right  넘는 경우 

코드

def solution(queue1, queue2):
    answer = 0
    q = queue1+queue2
    total = sum(q)
    if total% 2!=0: #전체 합이 홀수인 경우 불가능 
        return -1 
    goal = total//2
    
    cur_sum = sum(queue1)
    left, right = 0, len(queue1)-1
    while left<= right:
        if cur_sum== goal:
            return answer 
        elif cur_sum < goal: #큐의 합이 절반보다 작으면 right +1, right 범위를 벗어나면 종료  
            right += 1
            if right >= len(q): #범위를 벗어나면 종료 
                return -1 
            cur_sum += q[right]
            answer += 1
        else: #큐의 합이 절반보다 크면 left +1
            cur_sum -= q[left]
            left += 1
            answer += 1

    
    return -1