99클럽 코테 스터디 8일차 TIL, 프로그래머스 / 두 큐 합 같게 만들기

🔑 오늘의 학습 키워드 : Queue

🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/118667

 

from collections import deque

def solution(queue1, queue2):
    answer = 0
    
    q1 = deque(queue1)
    q2 = deque(queue2)
    
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    
    # 홀수인 경우
    if (sum1 + sum2) % 2 != 0:
        return -1
    
    while True:
        if answer == 4 * len(queue1):
            return -1
        
        if sum1 > sum2:
            value = q1.popleft()
            q2.append(value)
            sum1 -= value
            sum2 += value
        elif sum1 < sum2:
            value = q2.popleft()
            q1.append(value)
            sum1 += value
            sum2 -= value
        else:
            return answer
        answer += 1

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

틀린 풀이 

원형 큐라고 생각이 들었다

queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]

 

이렇게 큐가 2개가 있는데 둘이 합치면

 

queue = [3, 2, 7, 2, 4, 6, 5, 1]

 

이렇게 된다.

 

전체 합을 구해놓고 절반의 값에 해당하는 부분에서 나누면 된다고 생각했다.

from collections import deque

def solution(queue1, queue2):
    answer = 1
    queue = deque(queue1+queue2)
    total = sum(queue1) + sum(queue2)
        
    if (total) % 2 != 0:
        return -1
    
    target = total // 2
    
    while answer <= 2 * total :
        tmp = 0
        for idx,i in enumerate(queue):
            tmp += i
            if tmp > target:
                queue.append(queue.popleft())
                answer += 1
                break
            if idx >= len(queue1):
                answer += 1
            elif tmp == target :
                return answer
    return -1

 

하지만 이렇게 풀면 안됐던 것 같다.

 

1. sum()함수를 계속하는 것과 다름이 없고

2. 문제에서 구하라고 하는 pop() 연산 횟수에 대해 명확히 구분하지 못했어서 비효율적인 풀이었기 때문이다.

 

⏰ 예상 시간 복잡도 O(4 * len(queue)) = 1.2 * 10 ^ 6

제한 사항

1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
1 ≤ queue1의 원소, queue2의 원소 ≤ 109

 

😎 알고리즘 개요

두 큐를 만들고 각각 구하고자 하는 값보다 크면 자기의 앞에서 떼서 다른 큐에 넣어주는 알고리즘이다.

 

이때 sum을 계산을 계속하게 되면 시간초과가 나므로 값으로 계산을 해줬다.

 

그렇게 전체 사이클을 2번 돌렸는데도 답을 찾지 못하면

 

최악의 경우 모든 요소를 한 큐에서 다른 큐로 옮긴 후, 다시 원래 위치로 돌려놓아야 하는 경우가 되기 때문에 

 

( len(q1) + len(q2) )* 2으로 종료 조건을 설정해준다.

 

✅ 오늘의 회고

 

- 큐 2개를 선언해서 풀기

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL