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

0.  문제 링크

 

 

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

프로그래머스

---

1.  풀이 방법

 

 

1. 이 문제는 큐 두 개를 완전 탐색으로 해결하면 안 된다. 큐의 길이는 최대 300,000이기 때문에, 시간 초과가 날 우려가 있다.
2. 따라서 문제를 조금 더 멀리서 생각을 해보면, 모든 원소의 순서는 일정하다로 결론이 난다.
3. 따라서 Circle Queue처럼 생각할 수 있다. 그 원형 큐에서 적당히 가림막을 설치하고, 가림막 안의 원소와 가림막 밖의 원소의 합이 같으면 된다.
4. 두 번째 예시인 [1, 2, 1, 2], [1, 10 1, 2]를 보고, 원형 큐를 그리고, 가림막을 설치해 보자.

1. 그림이 쫌 짜치긴한데, 아무튼 이렇게 생각해서 원형 큐를 만들어서 가림막(포인터)을 옮기면 된다.
2. 이때 나는 원소의 합이 큰 쪽에서 원소를 빼서 작은 쪽에 넣었다. 그리고 그에 맞게 합과 포인터도 수정한다.
3. 만약 가림막인 left, right가 같은 위치가 되거나, left 혹은 right 둘 중 하나라도 제자리에 돌아온다면 끝내야 된다.
4. 같은 위치가 되면 해결법이 없다는 뜻이고, 둘 중에 하나가 제자리에 돌아온다는 것은 내부에 사이클이 존재한다는 뜻이다.

---

2.  코드

 

 

def solution(queue1, queue2):
    answer = 0
    
    queue = queue1 + queue2     # 하나의 리스트로 생각함. 중간에 포인터로 가림막을 넣어준다고 생각하면 편함
    
    left, right, sumL, sumR = 0, len(queue1), sum(queue1), sum(queue2)
    oriLeft, oriRight = left, right
    l = len(queue)
    
    if (sumL + sumR) % 2:
        return -1
    
    while (left) % l != (right) % l:        # Circle Queue처럼 생각하기, 만나면 해결이 불가능
        if sumL == sumR:
            return answer
        
        elif sumL < sumR:
            sumR -= queue[right]
            sumL += queue[right]
            right = (right + 1) % l
            
            if oriRight == right:       # 기존 포인터 위치로 돌아오면 특정 값들이 계속해서 반복된다고 볼 수 있음. -> -1 반환
                break
        
        elif sumL > sumR:
            sumL -= queue[left]
            sumR += queue[left]
            left = (left + 1) % l
            
            if oriLeft == left:
                break
            
        answer += 1
        
    return -1

---

3.  마무리