[ 프로그래머스 ] 두 큐 합 같게 만들기

 

1차시도. 풀이시간 15분. 대부분 시간초과

def solution(queue1, queue2):
    answer = -1
    n = len(queue1) + len(queue2)
    cnt = 0
    target = (sum(queue1) + sum(queue2))//2
    print(target, sum(queue1), sum(queue2))  
    
    while sum(queue1) != target:
        if cnt == n:
            break
        caseA = abs(sum(queue1) + queue2[0] - sum(queue2[1:]))
        caseB = abs(sum(queue2) + queue1[0] - sum(queue1[1:]))
        if caseA < caseB:
            queue1.append(queue2.pop(0))
        else:
            queue2.append(queue1.pop(0))
        cnt += 1
        
    if cnt != n:
        answer = cnt
        
    return answer

#1. 실패

# 2 ~ 10. 13 ~ 14, 16 ~ 18, 25 ~ 27, 29 성공

# 11 ~ 12, 15, 19 ~ 24, 28, 30 시간 초과

 

queue들 길이 보고 시간초과 나올 것 예상은 했는데 일단 문제 읽자마자 그대로 접근해봤다. 

qeque을 써야할 것이라고 생각해서 사용했는데 

음 .. ? 시간초과가 더 난다..! ㅋㅋㅋㅋ 아예 뭔가 잘 못 생각한건지..

 

조금 검색해봤는데 로직 자체는 그냥 저렇게 가져가면 되는데 while문이 아니라 for문으로 범위가 너무 튀어나가지 않게 관리해줘야하나보다.  +  sum 변수로 만들어서 리스트에 직접 접근하는 횟수를 줄이시더라.

 

---

 

2차 시도. 풀이 시간 10분. 1번 실패, 29개 테케 성공

from collections import deque
def solution(queue1, queue2):
    queue1, queue2 = deque(queue1), deque(queue2)
    sum1, sum2 = sum(queue1), sum(queue2)
    
    for i in range(len(queue1) + len(queue2) + 1):
        if sum1 == sum2:
            return i
        if sum1 > sum2:
            num = queue1.popleft()
            queue2.append(num)
            sum1 -= num
            sum2 += num
        else:
            num = queue2.popleft()
            queue1.append(num)
            sum1 += num
            sum2 -= num
    return -1

 

뭐지 1번..? 시간초과도 아니고 그냥 틀려버린다..

왜 .. 때문에..?

 

 

 

너무하다.. 실전에서 이걸 찾아낼 수 있을까 ? ㅠㅜㅠㅜ

 

각 큐의 길이 더해주고 1만 추가로 더했는데 그걸 10 더하는 걸로 바꾸니까 통과되었다.

  for i in range(len(queue1) + len(queue2) + 10):