22년도 카카오 인턴십 - 두 큐 같게 만들기

코딩테스트 연습 - 두 큐 합 같게 만들기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

• 두 큐 합 같게 만들기

문제 설명

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(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 해주세요.

---

제한사항

• 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
• 1 ≤ queue1의 원소, queue2의 원소 ≤ 109
• 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

---

입출력 예queue1queue2result

[3, 2, 7, 2]	[4, 6, 5, 1]	2
[1, 2, 1, 2]	[1, 10, 1, 2]	7
[1, 1]	[1, 5]	-1

---

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

두 큐에 담긴 모든 원소의 합은 20입니다. 따라서, 각 큐의 합을 10으로 만들어야 합니다. queue2에서 1, 10을 순서대로 추출하여 queue1에 추가하고, queue1에서 1, 2, 1, 2와 1(queue2으로부터 받은 원소)을 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [10], queue2는 [1, 2, 1, 2, 1, 2, 1]가 되며, 각 큐의 원소 합은 10으로 같습니다. 이때 작업 횟수는 7회이며, 이보다 적은 횟수로 목표를 달성하는 방법은 없습니다. 따라서 7를 return 합니다.

입출력 예 #3

어떤 방법을 쓰더라도 각 큐의 원소 합을 같게 만들 수 없습니다. 따라서 -1을 return 합니다.

 

---

[코드 해설]

그럼 이제 풀이를 들어가면 간단하게.

1. 큐 라이브러리를 이용하여 문제를 푼다 => 일반 리스트로 풀면 시간 초과가 걸림.

2. q1합과 q2의 합 중 큰 쪽을 작은 쪽으로 옮기는 과정을 거치면서 결론적을오 q1 과 q2의 합을 같게 만듭니다.

3. 대충 q1 * q2의 곱의 수만큼 해당 과정을 거치는데 문제를 풀었는데도 답이 안나오면 -1를 리턴하는 방식으로 문제를 풀었습니다.

*. 번외) 각각 while문이든 for문이든 그 안에서 일일이 합을 구하면 마찬가지로 시간초과가 나옵니다. 때문에, 처음 합을 구한후 popleft, append 하면서 합들을 +, - 하는식으로 각각의 합을 최신화해야 시간초과를 면할 수 있습니다.

 

---

[코드]

from collections import deque


def solution(queue1, queue2):
    answer = 0
    q1 = deque(queue1)
    q2 = deque(queue2)
    s1 = sum(q1)
    s2 = sum(q2)
    
    total = len(q1) * 3
    while s1 != s2:
        if s1 > s2:
            n = q1.popleft()
            q2.append(n)
            s2 += n
            s1 -= n
            answer += 1
        else:
            n = q2.popleft()
            q1.append(n)
            s2 -= n
            s1 += n
            answer += 1

        if answer == total:
            return -1
    return answer

 

---

후기

 

이 문제 괜히 어렵게 생각했습니다.

두 큐의 차가 2라면 각각 1차이나는 원소를 바꾸고, 하나의 원소 불가능하면 부분 집합을 찾으면서 하려고 했는데...

그런 수준의 로직을 짜는거면 예.. 이게 레벨2가 아니겠죠.. 사실 문제의 레벨에 대해서는 신경쓰지 않습니다만 실전에서는 레벨을 안보여주니까요.

지금 생각해보면 일단 바로 생각나는 로직을 짜서 제출 후 천천히 최적화하는 과정을 거치는게 옳은 방법인거 같네요