[프로그래머즈 Lv2, Java] 두 큐 합 같게 만들기

길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(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://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

---

문제는 심플하다.

Queue기 때문에, 앞에서 부터 순서대로 pop해서 계산하면되고, 이를 위해 합이 큰쪽에서 적은쪽을 빼서 진행하면된다.

그리고 불가능한 방법을 판별하는 방법은, 큐가 한 바퀴 돌았는데 합이 같아지지 않았다면 불가능하다.

 

예를들어

{1, 1}과 {3,4}가 있다면

 - 1+1 < 3+4 이므로, 3을 pop해서 넘겨줌

 - 1+1+3 > 4 이므로, 1을 pop해서 넘겨줌

 - 1+3 > 4 + 1 이므로, 4를 pop해서 넘겨줌

 - 1+3+4 > 1 이므로, 1을 pop 해서 넘겨줌

이렇게 {3,4}, {1,1}로 한바퀴를 돌았는데, 합이 같아지지 못했으니 불가능한 예시이다.

 

이를 구현하기 위해서, queue1이 자신의 것을 모두 pop했다면 queue2의 0부터 다시 pop하는 방식으로 했다.

queue2의 0부터 pop되서 queue1의 뒤에 붙으므로, 결과적으론 아무 차이도 없기 때문이다.

 

IndexOutOfBounds 로 예외처리를 한이유는 괜히 뭐 queue1.length.. 이런걸로 조건처리 하는것보다 이게 좀 더 직관적으로 보이기 때문이다.

만약 한 바퀴를 다 돌리고나서 추가로 참조하려하면 예를들어 위에서 든 예시같은 경우면 queue[3]막 이렇게 참조하게 되버릴테니 IndexOutOfBoundsException이 날 것이다.

(하지만 제출은 Exception으로 제출했다)

 

솔직히 효율성 검사 있을줄알고 이런식으로 짠건데 없어서 좀 아쉬웠다.