[Python | 프로그래머스] 2022 KAKAO : 두 큐 합 같게 만들기

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

프로그래머스

 

문제

제한사항

 

내 풀이1

이 문제는 결국 시간초과와 싸우는 문제였다. while문 안에서 sum([리스트])를 하거나 [리스트].pop(0) 등을 사용하면 높은 확률로 시간초과아 맞닥뜨리기 때문에

while문 이전에 sum([리스트])를 한 후에 반복문 안에서는 사칙연산만 사용하던가, 

deque를 활용하여 pop(0)대신 popleft()를 사용하는 등으로 변경해줘야 한다. 

from collections import deque

def solution(queue1, queue2):
    answer = 0
    queue1, queue2 = deque(queue1), deque(queue2)
    sum1, sum2 = sum(queue1), sum(queue2)
    if (sum1 + sum2) % 2 == 1:
        return -1
    else:
        target = (sum1 + sum2)//2

    while True:
        if sum1 == target:
            break
        elif (len(queue1) + len(queue2))+1< answer:
            answer = -1
            break
        if sum1 > target:
            temp = queue1.popleft()
            queue2.append(temp)
            sum1 -= temp
            sum2 += temp
            answer += 1
        else:
            temp = queue2.popleft()
            queue1.append(temp)
            answer += 1
            sum2 -= temp
            sum1 += temp
    return answer
solution(queue1, queue2)

내 풀이2

문제를 풀다가 생각한 방식인데, deque를 사용하지 않고 풀 수 있다. 

결국 queue를 그대로 두고 sum이 같아 질때까지 앞에서만 빼고, 뒤로만 추가하므로 

queue1 + queue2 + queue1 식으로 이어서 잘라가면서 확인이 가능하다. 

 

입출력 예로 설명하면 queue1 = [3, 2, 7, 2], queue2 = [4, 6, 5, 1] 일때 

queue1의 합 = 14, queue2의 합 = 16 이다. 최종적으로 둘의 합의 절반인 15를 만드는 과정이 반복되니

합의 수가 더 작은 queue1을 기준으로 

total = queue1 + queue2 + queue1  = [3, 2, 7, 2, 4, 6, 5, 1, 3, 2, 7, 2] 형태로 만들어주고 

3 2 7 2 부터 시작해서 15보다 작다면 계속 뒤의 숫자를 추가 해주고

16보다 크다면 앞에 숫자인 3부터 하나씩 빼도록 반복하는 것이다. 

그렇게 15가 나올때까지 반복하면 된다. 

 

3 2 7 2의 합은 14이므로 뒤에 4를 더해주고, ( = 3 2 7 2 4)

15가 넘어서 앞에 3을 빼줘서 2 7 2 4를 만든다. 

이러면 합이 15가 되므로 반복문을 종료하고, 2번의 과정을 거쳤으므로 답을 2로 출력하면 된다.

def solution(queue1, queue2):
    answer = 0
    sum1, sum2 = sum(queue1), sum(queue2)
    if (sum1 + sum2) % 2 == 1:
        return -1
    else:
        target = (sum1 + sum2)//2

    if sum1 < sum2:
      total = queue1 + queue2 + queue1
    else:
      total = queue2 + queue1 + queue2
    
    start_pos = 0
    end_pos = len(queue1)
    sum_chk = sum(total[:end_pos])

    while True:
        if sum_chk == target:
            break
        elif (len(queue1) + len(queue2))+1< answer:
            answer = -1
            break        

        while sum_chk < target:
          sum_chk += total[end_pos]
          end_pos += 1
          answer += 1

        while sum_chk > target:
          sum_chk -= total[start_pos]
          start_pos += 1
          answer += 1
          
    return answer