[알고리즘] 프로그래머스 - 두 큐 합 같게 만들기

문제

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

프로그래머스

 

 

풀이

처음에 봤을 때 일반적인 구현은 금방 할 것 같았는데 -1를 출력하는 경우를 어떻게 판단할지가 고민이었다.

나는 각 큐의 길이가 300,000 이하이므로 600,000 번 이상 교환을 했는데도 두 큐의 합이 같지 않다면 합을 같게 만들 수 없다고 판단하고 -1을 리턴해주는 식으로 해줬다. 정답처리는 됐지만 이 숫자를 어떤 기준으로 잡아야하는지는 모르겠다...

다른 사람들을 어떻게 지정했을까 궁금해서 봤는데... 1,000,000번도 있고, 300,000번도 있고.. 다들 제각각 이더라. 흠 또.. 4*len(queue1) + 1 로 잡은 분들도 있고 , 2* len(queue1) * len(queue2) 로 잡은 분들도 있던데 .. 어떻게 잡아야 정확한 풀이인건지를 모르겠다 (아는 분 계시면 댓글 남겨주세요...)

 

일반적인 상황에서의 구현은 간단하다. 처음에 각 큐의 sum을 구한다. 그 뒤로도 sum함수를 통해 구하려고 했는데 시간 초과가 날 것 같아서 while 문 내에서는 처음 구한 sum에서 더하고 빼주는 방식으로 합을 구했다. 아마 sum함수를 썼으면 시간 초과가 났을 것 같다...! 합이 더 큰 큐에서 원소를 뽑아 넣는 방식으로 구현하면 최소 횟수로 같은 합 큐를 만들 수 있다.

 

정답 코드

from collections import deque
def solution(queue1, queue2):
    answer = 0
    
    q1 = deque(queue1)
    q2 = deque(queue2)

    number = sum(q1) + sum(q2)
    
    if number % 2:
        return -1
    
    q1_sum = sum(q1)
    q2_sum = sum(q2)
    
    while q1_sum != q2_sum:
        if answer > 600000:
            return -1
            
        if q1_sum < q2_sum:
            answer += 1
            a = q2.popleft()
            q1.append(a)
            q1_sum += a
            q2_sum -= a
        else:
            answer += 1
            a = q1.popleft()
            q2.append(a)
            q2_sum += a
            q1_sum -= a
    
    return answer