📝 문제
💡 길이가 같은 두 개의 큐가 주어집니다.
하나의 큐를 골라 원소를 추출(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의 원소 ≤ 10^9
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
✅ 풀이
from collections import deque
def solution(queue1, queue2):
answer = 0
queue1, queue2 = deque(queue1), deque(queue2)
onehap = sum(queue1)
twohap = sum(queue2)
hap = onehap + twohap
if hap % 2 == 1:
answer = -1
else:
while queue1 and queue2:
if hap // 2 == onehap:
return answer
elif onehap > hap // 2:
target = queue1.popleft()
onehap -= target
answer += 1
else:
target = queue2.popleft()
queue1.append(target)
onehap += target
answer += 1
return -1💡 두 큐를 모두 대상으로 하여 작업을 하면 채점시 딱 하나의 케이스에서 시간초과가 생겼다.
따라서, 하나의 큐만 주목하여 두 큐가 모두 비워지기 전까지 작업을 진행했다.
매번 큐의 합을 sum으로 구하면 그것 또한 시간 초과의 요인이 되기 때문에,
처음에 구해둔 합을 기준으로 작업을 진행했다.
1번 큐의 합이 목표값보다 크다면 첫번째 원소를 pop하여 버리고, 합에서 빼줬다.
이 때 1번 큐만 주목하여 작업할 것이므로, 버린 원소를 2번 큐에 넣을 필요가 없다.
1번 큐의 합이 목표값보다 작다면, 2번 큐의 첫번째 원소를 pop해서 1번 큐에 push했다.
이 때도 마찬가지로 1번 큐만 주목하기 때문에, 1번 큐의 합에만 더해주면 된다.
그렇게 작업했을 때 1번 큐의 합이 목표값과 같아지면 answer를 리턴하고,
둘 중 한 큐가 다 비워졌는데도 그렇지 못했다면 -1을 리턴하도록 했다.
