[프로그래머스 | Lv2] 두 큐 합 같게 만들기 (Python) - 2022 KAKAO TECH INTERNSHIP

 

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

프로그래머스

 

두 큐의 합을 2로 나눈 값이 홀수이면 바로 -1을 리턴한다. (두 큐의 합을 같게 만들 수 없다.)

두 큐의 합을 2로 나눈 값을 target으로 설정해주고, 큐1의 합을 left로 설정해준다.

그 후 반복문을 돌면서 left < target이면 큐2에서 원소를 꺼내 큐1에 넣어주고, 

left > target이면 반대로 큐1에서 원소를 꺼내 큐2에 넣어주고,

left == target이면 그대로 정답을 리턴해주면 된다!!

반복문이 모두 끝났다면 두 큐의 합을 같게 만들 수 없기 때문에 -1을 리턴해준다.

 

# 프로그래머스 118667: 두 큐 합 같게 만들기 (2022 KAKAO TECH INTERNSHIP)

from collections import deque

def solution(queue1, queue2):
    if (sum(queue1) + sum(queue2)) % 2 != 0:
        return -1
        
    target = (sum(queue1) + sum(queue2)) // 2
    left = sum(queue1)
    
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    answer = 0
    
    while queue1 and queue2:
        if left < target:
            q = queue2.popleft()
            queue1.append(q)
            left += q
            answer += 1
        elif left > target:
            q = queue1.popleft()
            queue2.append(q)
            left -= q
            answer += 1
        else:
            return answer
        
    return -1

 

하지만 tc28에서 시간 초과가 났고, 직접 반례를 넣어보니 반복문을 무한으로 돌고 있는 현상을 발견했다.

그래서 처음의 큐를 저장해놓고, 큐가 같으면 -1을 리턴하는 코드를 넣었는데..

 

# 프로그래머스 118667: 두 큐 합 같게 만들기 (2022 KAKAO TECH INTERNSHIP)

from collections import deque

def solution(queue1, queue2):
    if (sum(queue1) + sum(queue2)) % 2 != 0:
        return -1

    target = (sum(queue1) + sum(queue2)) // 2
    left = sum(queue1)
    
    q1 = deque(queue1)
    q2 = deque(queue2)
    answer = 0
    
    while q1 and q2:
        if left < target:
            q = q2.popleft()
            q1.append(q)
            left += q
            answer += 1
        elif left > target:
            q = q1.popleft()
            q2.append(q)
            left -= q
            answer += 1
        else:
            return answer
        
        if q1 == deque(queue1) or q1 == deque(queue2):
            return -1
        
    return -1

 

ㅎㅎ 더더욱 심각한 시간 초과가 났다..;

그래서 다시 반례로 계산해보다가

큐의 길이(문제에서 주어진 두 큐의 길이는 같다.) * 4번 이상의 반복문을 돌면

결국 처음의 큐로 돌아온다는 사실을 발견했다!

 

# 프로그래머스 118667: 두 큐 합 같게 만들기 (2022 KAKAO TECH INTERNSHIP)

from collections import deque

def solution(queue1, queue2):
    if (sum(queue1) + sum(queue2)) % 2 != 0:
        return -1

    length = len(queue1) * 4
    target = (sum(queue1) + sum(queue2)) // 2
    left = sum(queue1)
    
    q1 = deque(queue1)
    q2 = deque(queue2)
    answer = 0
    
    while q1 and q2:
        if left < target:
            q = q2.popleft()
            q1.append(q)
            left += q
            answer += 1
        elif left > target:
            q = q1.popleft()
            q2.append(q)
            left -= q
            answer += 1
        else:
            return answer
        
        if answer >= length:
            return -1
        
    return -1

 

무사히 통과..😭