[python] 두 큐 합 같게 만들기(+투 포인터 방식)

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

프로그래머스

---

• 큐의 길이 * 4를 하는 이유 : https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/

 처음 떠올린 풀이가 투포인터여서 카운트 조건을 주는 건 이해하기 어렵지 않았다

 

from collections import deque
 
def solution(queue1, queue2):
    q1, q2 = deque(queue1), deque(queue2)
    s1, s2 = sum(q1), sum(q2)
    cnt = 0
    limit = len(q1) * 4
    while (q1 and q2) and cnt < limit:
        if s1 == s2:
            return cnt
        elif s1 > s2:
            temp = q1.popleft()
            q2.append(temp)
            s1 -= temp
            s2 += temp
        elif s1 < s2:
            temp = q2.popleft()
            q1.append(temp)
            s1 += temp
            s2 -= temp
        cnt += 1
    
    return -1

 

---

투 포인터 방식( 런타임 에러) -> 테스트 케이스 11, 28번 런타임 에러

def solution(queue1, queue2):
    q = queue1 + queue2
    goal = sum(q)//2
    limit, cnt = len(q) * 2, 0
    left, right = 0, len(queue1)
    s_left = sum(q[left:right])
    while left < right and cnt <= limit:
        if s_left < goal:
            s_left += q[right]
            right += 1
        elif s_left > goal:
            s_left -= q[left]
            left += 1
        elif s_left == goal:
            return cnt
        cnt += 1
    return -1

---

투포인터 정답 풀이

• right < len(q) and cnt < limt 조건으로 변경
• 파이썬은 cnt <= limit 조건만 주면 IndexError: list index out of range 가 뜬다
• cnt 조건 + left < right 조건에서는 left가 right보다 작더라도 right가 리스트의 끝을 넘어가는 케이스가 있기 때문에 런타임에러가 뜬다
• 다른 사람들의 자바스크립트+ 투포인터 풀이를 보면 포인터의 조건을 주지 않아도 통과가 된다 이유를 모르겠다..🥲

 

def solution(queue1, queue2):
    q = queue1 + queue2
    goal = sum(q)//2
    limit, cnt = len(q) * 2, 0
    left, right = 0, len(queue1)
    s_left = sum(q[left:right])
    while right < len(q) and cnt <= limit : 
    # 테스트케이스 3번의 경우 right 포인터가 q의 길이를 넘어가면서 out of index 에러가 뜸 
    # -> right가 q의 끝에 다다르면 해결불가능으로 보고 종료 -> -1 출력
        if s_left < goal:
            s_left += q[right]
            right += 1
        elif s_left > goal:
            s_left -= q[left]
            left += 1
        elif s_left == goal:
            return cnt
        cnt += 1
    return -1