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

이강혁·2024년 7월 30일
0

프로그래머스

목록 보기
60/82

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

두 개의 큐가 주어지고, 각각 헤드에서 뽑은 값을 다른 큐의 테일에 넣을 수 있는 연산이 있고 그렇다.

처음에는 각각 뽑아보면서 테스트해야 싶었으나 그러면 연산이 너무 많아질 것 같아서 다른 방법을 찾아봤다.

queue1의 앞에서 뽑아서 queue2의 뒤로 가고, queue2의 앞에서 뽑아서 queue1의 뒤로 가면

이런 모양이기에 queue1을 뒤집으면

이렇게 되기에 두 큐를 합칠 수 있겠다 생각했다.
그래서 큐 두 개를 합치고 슬라이딩 윈도우로 해보았다.

def solution(queue1, queue2):
    answer = -2
    
    total = sum(queue1) + sum(queue2)
     
    if total %2 != 0:
        return -1
    
    target = total // 2
    
    combined = queue1 + queue2
    
    n = len(queue1)
    
    left = 0
    right = n - 1
    
    current = sum(queue1)
    
    count = 0
    
    while left < len(combined):
        if current == target:
            break
                
            
        if current<target:
            right += 1
            right %= 2 * n
            current += combined[right]
            count += 1
    
        else:
            current -= combined[left]
            left += 1
            count += 1
            
    return count if current == target else -1

큐 두 개를 합치고 슬라이딩 윈도우의 합을 전체 합의 1/2와 비교하면서 했다.

queue1부터 시작해서 left가 끝에 도달하지 않을 동안 크기를 비교하면서 크다면 left를 한 칸 오른쪽으로 옮기고, 작다면 right를 늘려서 증가시키고, 만약 right가 범위를 벗어나면 0번 인덱스로 옮겨서 더해줬다.

그래서 마지막에 left가 combined의 끝에 닿아서 멈추거나 current == target이 돼서 멈췄을 경우 current == target인지 비교해서 count나 -1을 출력했다.

profile
사용자불량

0개의 댓글