두 큐 합 같게 만들기 - Programmeres

코딩테스트 연습 두 큐 합 같게 만들기

이번에 새롭게 푼 문제에서 시간 복잡도에 대한 고민을 해본 문제입니다.

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

문제는 위 링크에서 참고하시면 될 것 같아요! 제가 틀렸었는지도 공유해드리려고 합니다!

생각한 아이디어

• 둘 합의 평균보다 큰 값이 원소에 있으면 아무리 교환해도 같게 만들 수 없음
• 총합이 홀수라면 같게 만들 수 없음
• list는 시간 복잡도가 크므로 queue를 사용
• 한 바퀴가 모두 돌아 자기자신이 되면 불가능한거니까 break

틀렸던 내용은 주석으로 처리한 정답 코드 공유드립니다!

from collections import deque

def solution(queue1, queue2):
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    answer = 0
    s1 = sum(queue1)
    s2 = sum(queue2)
    total_sum = s1+s2
    mean = total_sum//2
    if mean<max(queue1) or mean<max(queue2):
        return -1
    if total_sum%2==1:
        return -1
    #t1= queue1.copy()
    #t2 = queue2.copy()
    t_len=len(queue1)
    while True:
        if s1==s2:
            break
        elif s1<s2:
            value = queue2.popleft()
            queue1.append(value)
            s1+=value
            s2-=value
        else:
            value = queue1.popleft()
            queue2.append(value)
            s1-=value
            s2+=value
        answer+=1
        if t_len*4<answer:
            return -1
        #if t1== queue1 and t2 ==queue2:
        #    return -1

    return answer

틀렸던 부분은 아래와 같아요. 대소 비교에 대해 O(1)이라고 생각을 했어서 t1과 t2가 queue1,queue2와 같은지를 비교하는지에 대해 O(1)이라고 생각헀습니다.. 하지만 O(len(N))이어서 시간초과가 계속 나더라고요..ㅠㅠ 그리고 추가적으로 sum()함수도 처음엔 사용했었는데 O(N)이어서 while 안에서 반복하는 것은 시간초과를 낼 수 있어요. 간단한 트릭으로 queue에서 하나를 빼서 넣고를 하는거니 초기 각 queue의 sum값에서 +와 -를 하면 O(1)로 해결할 수 있습니다!

이전까지는 단순히 반복문에 대해서만 시간 복잡도를 계산하였는데 이번에 조금 더 배웠던 거 같네요. 모두 화이팅입니다 ㅎㅎ