📍문제

[프로그래머스] Lv.2 두 큐 합 같게 만들기 (Python)

📍풀이

📖queue?

• 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO)형태의 자료구조
• 큐는 입구와 출구가 모두 뚫려 있는 터널 같은 형태이다.
• list 와 다르게 가장 앞의 원소를 삭제하려면 .popleft()를 사용한다.
  

📖나의 솔루션

1. 제목부터 두 큐 합 같게 만들기여서 from collections import deque로 deque라이브러리를 import 해줬다.
2. q1, q2 = deque(queue1), deque(queue2)로 큐 생성
3. q1_sum, q2_sum = sum(q1), sum(q2)로 q1, q2의 합을 각각 만들어준다.
4. q1_sum이 q2_sum보다 크면 q1에서 가장 첫번째 원소를 pop해서 빼준 다음, q2에 append해준다. 또한 q2_sum에 그 값을 더해준다.
5. 이렇게 연산이 발생할 때 마다 개수를 더해주고 결과값을 return한다.

💻코드

첫번째 풀이

from collections import deque
def solution(queue1, queue2):
    q1, q2 = deque(queue1), deque(queue2)
    q1_sum, q2_sum = sum(q1), sum(q2)
    cnt = 0    
    while q1 and q2: # 큐가 빌 때 까지
        if q1_sum == q2_sum:
            return cnt
        elif q1_sum > q2_sum:
            num = q1.popleft()
            q2.append(num)
            q1_sum -= num
            q2_sum += num
            cnt+= 1
        else: # q2_sum이 q1_sum보다 클 때
            num = q2.popleft()
            q1.append(num)
            q2_sum -= num
            q1_sum += num
            cnt+= 1
    return -1 # 값이 같아지지 않으면 -1을 반환

이렇게 작성하면 코드실행해서 나오는 테스트케이스 3개는 통과하지만 테스트11과 테스트28에서 시간초과가 뜬다.
강사님한테도 여쭤보고 구글링을 해본 결과 두 큐의 합이 1밖에 차이가 안나는 경우 while문을 탈출하지 못하여 무한루프에 걸리게 되어 시간초과가 되는 것..
예를들어 두 큐가 각각 [1, 1], [1,2]이렇게 구성되어 있을 경우 각 큐에서 1을 더해주고 빼주는 행위가 계속 일어나서 무한루프에 빠지게 되는 것이다.
해결방법은 for 문을 이용해서 range를 정해주거나, while문에 종료조건을 포함해주면 된다!
나는 for문을 이용해서 코드를 다시 짰다.(while문을 이용할 경우 cnt가 30000이 되는 경우 break하는 형태로 작성하면 된다.)

두번째 풀이

from collections import deque
def solution(queue1, queue2):
    q1, q2 = deque(queue1), deque(queue2)
    q1_sum, q2_sum = sum(q1), sum(q2)
    for i in range(300000):
        if q1_sum == q2_sum:
            return i
        elif q1_sum > q2_sum:
            num = q1.popleft()
            q2.append(num)
            q1_sum -= num
            q2_sum += num
        else: # q2_sum이 q1_sum보다 클 때
            num = q2.popleft()
            q1.append(num)
            q2_sum -= num
            q1_sum += num      
    return -1 # 값이 같아지지 않으면 -1을 반환

제한사항에서 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000라고 했으므로 범위를 300000으로 잡아서 for문을 돌려주었다. 이렇게 하면 테스트11과 테스트28에서도 시간초과가 뜨지 않는다!!😁