[프로그래머스] [KAKAO] Lv.2 두 큐 합 같게 만들기 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/118667
• 2022 KAKAO TECH INTERNSHIP 기출문제

 

• 문제 그대로 구현은 간단했는데 11번, 28번 테스트 케이스에서 계속 시간 초과가 뜸
• 큐의 길이가 30만 까지라서 큐의 길이가 너무 길 때 시간 초과가 뜬 줄 알았다...
• 원래 q1Sum, q2Sum 없이 while 문 안에서 sum(queue1) 처럼 sum함수를 계속 써서 비교를 했다.
• 하지만 시간 초과로 인해 시간을 줄이려고 sum 함수를 한 번씩만 사용하고 그 값에 더하고 빼는 방법을 사용
• 그래도 마찬가지로 11, 28번 테스트 케이스에서 시간 초과
• 몇 가지 테스트 케이스로 디버깅을 해보니 무한 루프가 도는 상황이 발생
  • queue1 = [101, 100], queue2 = [102, 103]
  • 이 케이스에서 두 큐의 합을 같게 하려면 각 큐가 203이 돼야 하는데 무한 루프가 돔
  • 해결 방법 : 작업 횟수가 두 큐의 길이보다 길어지면 -1을 리턴 시킴
  • 여기서 두 큐의 길이가 4인데 작업을 4번 하면 원래의 상태로 돌아온다.
  • queue1과 queue2의 원본이 서로 교체가 됐다는 말이 맞는 것 같다.
  • 요소만 봤을 때 돌고 돌아 원래의 상태로 돌아왔다는 건 = 계속 돌아도 답이 나오지 않는다.
• 위처럼 무한 루프가 돌 때의 종료 조건을 주니 11, 28번 모두 통과 !

작업 횟수	타겟 = 203	0	1	2	합
원본	queue1	101	100		201
원본	queue2	102	103		205
1	queue1	101	100	102	303
1	queue2	103			103
2	queue1	100	102		202
2	queue2	103	101		204
3	queue1	100	102	103	305
3	queue2	101			101
4	queue1	102	103		205
4	queue2	101	100		201

from collections import deque

def solution(queue1, queue2):
    q1Sum = sum(queue1) # 큐1 요소들의 합
    q2Sum = sum(queue2) # 큐2 요소들의 합
    qlen = len(queue1) + len(queue2) # 두 큐의 길이의 합
    total = q1Sum + q2Sum   # 두 큐 요소들의 합
    target = total // 2     # 두 큐 합을 같게 만들기 위한 타겟 값
    cnt = 0             # 작업 횟수

    q1 = deque(queue1)  # popleft() 함수 사용을 위한 deque
    q2 = deque(queue2)  # popleft() 함수 사용을 위한 deque
    
    while q1 and q2: 
        if q1Sum == q2Sum: # 두 큐의 합이 같아지면 cnt 리턴
            return cnt
        if qlen < cnt:     # 작업 횟수가 두 큐 길이의 합 보다 커지면 작업 실패
            return -1
        if q1Sum > target:  # q1 요소의 합이 타겟 값 보다 크면
            while q1Sum > target:   # 타겟값보다 작아질 때 까지
                x = q1.popleft()    # q1에서 하나 빼서 x에 저장
                q2.append(x)        # 빼온 값을 q2에 삽입
                q1Sum -= x          # q1 요소의 전체합 = 빼낸 요소의 값을 뺀다
                q2Sum += x          # q2 요소의 전체합 = q1에서 빼낸 값을 더한다
                cnt += 1            # 작업 횟수 + 1
        elif target < q2Sum:        # q2 요소의 합이 타겟 값 보다 크면 위와 동일 작업 실행
            while target < q2Sum:
                x = q2.popleft()
                q1.append(x)
                q2Sum -= x
                q1Sum += x
                cnt += 1
            
    return -1