[python] programmers - 두 큐 합 같게 만들기

programmers - 두 큐 합 같게 만들기

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

프로그래머스

자세한 설명은 위의 링크를 참조하세요.

 

 

문제 설명

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.

큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.

다음은 두 큐를 나타내는 예시입니다.

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

두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다. 예를 들어, 다음과 같이 2가지 방법이 있습니다.

1. queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다.
2. queue1에서 3을 추출하여 queue2에 추가합니다. 그리고 queue2에서 4를 추출하여 queue1에 추가합니다. 그 결과 queue1은 [2, 7, 2, 4], queue2는 [6, 5, 1, 3]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 2번만 수행하며, 이보다 적은 횟수로 목표를 달성할 수 없습니다.

따라서 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수는 2입니다.

길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

 

문제 풀이

제일 먼저 생각해야할 것은 어떤 로직을 통해야 최소 작업 횟수를 구하는가 입니다. 가장 먼저 떠올린 방법은 그리디 알고리즘입니다. 

https://man-25-1.tistory.com/142?category=1041418 

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 따라서 각 큐의 원소 합을 같게 만들기 위한 그리디 알고리즘은 두 큐 중 합이 더 큰 큐에서 원소를 빼고, 나머지 큐에 넣는 것입니다.

 

처음에 위의 로직을 구현한 순서는 아래와 같습니다.

아래와 같이 두 큐가 존재할 때

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

1. 각 큐의 합을 구합니다.

2. 큐1, 큐2의 각각의 합을 비교합니다.

3. 합이 큰 큐에서 pop 하고, 작은 큐로 append합니다.

4. 1~3번 과정을 두 큐가 같아질때까지 반복합니다.

 

여기까지 구현하면 종료 조건에 대한 문제에 맞닥뜨리게 됩니다.

문제에서 어떤 방법으로도 각 큐의 합을 같게 만들지못할때는 -1을 반환하라고 했기때문입니다.

 

제가 떠올린 조건은 세가지정도였습니다. 

 

1. 각 큐가 empty 할 때

2. 각 큐가 반복 후 처음의 큐와 같아질 때

3. 무한 반복되는 구간이 있을때

 

이렇게하고 몇가지 테스트 케이스를 넣어본 결과 각 큐가 비게되면 순환되는 것을 확인할 수 있었습니다.

 

위의 로직을 코드로 구현해보면 아래와 같습니다.

from collections import deque def solution(queue1, queue2):     target_sum = (sum(queue1) + sum(queue2)) // 2     left_sum = sum(queue1)     right_sum = sum(queue2)          queue1 = deque(queue1)     queue2 = deque(queue2)     answer = 0          while queue1 and queue2:         if left_sum < right_sum:             tmp = queue2.popleft()             queue1.append(tmp)             left_sum = sum(queue1)             right_sum = sum(queue2)             answer += 1                      elif left_sum > right_sum:             tmp = queue1.popleft()             queue2.append(tmp)             right_sum = sum(queue2)             left_sum = sum(queue1)             answer += 1         else:             return answer     else:         return -1

그 결과...

즉 로직은 맞았지만, 시간복잡도를 개선하기 위해 수정을 해줘야할 것으로 보입니다.

 

1. 반복문에서 반복마다 sum함수를 호출하고 있는데, 이 부분은 left_sum,right_sum 변수를 둠으로써 바로 수정이 가능합니다.

2. 각 큐의 원소합을 같게 만들기 위해서는 left_sum과 right_sum을 비교하지 않아도 됩니다. 위의 예시에서도 알 수 있듯이, 각 큐의 합이 15인지만 확인하면 되기때문에 두 큐 중 한가지만 정해서 15(target_sum)와 비교하면 됩니다.

 

 

최적화한 코드는 아래와 같습니다.

from collections import deque def solution(queue1, queue2):     target_sum = (sum(queue1) + sum(queue2)) // 2     left_sum = sum(queue1)     queue1 = deque(queue1)     queue2 = deque(queue2)     answer = 0     while queue1 and queue2:         if left_sum < target_sum:             tmp = queue2.popleft()             left_sum += tmp             queue1.append(tmp)             answer += 1         elif left_sum > target_sum:             left_sum -= queue1.popleft()             answer += 1         else:             return answer     else:         return -1

각 반복에서 pop 1번 , append  1번, sum 2번 호출을 했었으나

최적화후 pop1번, append 0.5번 , sum 0번 호출로 변경되었습니다.

 

시간복잡도 상으로 sum은 O(n) , pop과 append는 O(1) 이기때문에 sum을 지운것만으로 아마 시간복잡도 문제는 해결될 것으로 보입니다.

통과 !