[Algorithm] 두 큐 합 같게 만들기

서른 한 번째 포스팅

안녕하세요! 서른 한 번째 포스팅으로 찾아뵙게 되어 반갑습니다!♥

오늘의 포스팅 내용은 프로그래머스 - 두 큐 합 같게 만들기에 관한 내용입니다.
자세한 내용을 알아보러 갑시다❗️

[Boongranii] Here We Go 🔥

---

1️⃣ 문제

[프로그래머스] 두 큐 합 같게 만들기 (문제 링크)

💨 문제 설명

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

💨 입출력 예

queue1	queue2	result
[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 합니다.

---

2️⃣ 문제 풀이

🔥 문제 풀이

1. 각 큐의 합을 구함.
2. 큐끼리의 합의 절반을 target에 저장함.
3. 큐1의 길이와 큐2의 길이의 합까지의 반복문을 돌림.
4. target과 큐1의 합이 같은 경우, 작은 경우, 큰 경우로 나눔.
5. shift() 연산은 시간 초과가 뜨기 때문에 인덱스를 이용하여 해결함.
6. maxLen은 큐1과 큐2의 길이의 합 * 3 - 3으로 설정함. - 아래 내용 참조 바람

function solution(queue1, queue2) {
  let count = 0;
  let isSame = false;
  let q1Index = 0,
    q2Index = 0;
  let maxLen = (queue1.length + queue2.length) * 3 - 3;

  let sumQueue1 = queue1.reduce((acc, curr) => acc + curr, 0);
  let sumQueue2 = queue2.reduce((acc, curr) => acc + curr, 0);
  let target = (sumQueue1 + sumQueue2) / 2;

  while (count < maxLen) {
    if (sumQueue1 === target) {
      isSame = true;
      return count;
    } else if (sumQueue1 < target) {
      const a = queue2[q2Index++];
      queue1.push(a);
      sumQueue1 += a;
    } else {
      const a = queue1[q1Index++];
      queue2.push(a);
      sumQueue1 -= a;
    }

    count++;
  }

  return isSame ? count : -1;
}

시간 초과와 통과되지 않는 TC 1번으로 인해 애를 먹은 문제이다.

먼저, shift() 연산은 O(n)의 시간 복잡도를 가진다. python에는 deque()라는 메서드가 존재하는가 보다. 양쪽 끝에서 요소를 추가하거나 제거하는 작업의 시간 복잡도는 O(1)이라고 한다. 이 deque()는 내부적으로 연결리스트와 유사한 구조를 사용하기 때문에 가능하다고 한다. 추가/제거 작업이 매우 빠르게 수행된다고 한다.

하지만 javascript에서의 shift()는 배열의 첫 번째 요소를 제거하고, 나머지 요소들을 한 칸씩 앞으로 이동시키기 때문에, 배열의 크기에 비례하는 시간이 소요된다. 그러므로 배열의 길이가 길어질수록 연산은 더욱 느려진다는 것이다.

문제 제한사항에서 배열의 최대 길이는 300,000이라고 한다. 절대로 shift()를 사용해서는 시간 초과만을 겪고 말 것이다. 따라서, 이 연산을 배제하고 index를 통해서 해결했다.

그래서 내 코드를 보면 저렇게 index 값을 올려주며 수행하는 모습을 확인할 수 있다. 저렇게 하면 공간복잡도가 커진다는데 별 수 있나. 문제는 풀어야 하는데.

저렇게만 바꾸면 끝인 줄 알았으나,, 시간 초과는 나지 않았지만 통과되지 않는 테스트 케이스가 내 발목을 잡았다. 발목을 잡은건가 손목을 잡은건가 내 눈을 잡은건가 몰라

어쨌든, 본론은 이제부터다. 질문하기를 참고해 보았다. 다들 시간 초과와 탈출 조건에 대해 논하고 있었다. 해결 방안은 역시나 존재했다.

바로 최대 작업 횟수 구하기가 키 포인트였다.

[출처-Developer_TaeHui님의 블로그]

문제의 큐를 예를 들어 설명했다.

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

큐의 특성에 따라 원형으로 표시했다. 좌측이 queue2이고 우측이 queue1이다. queue를 구분하는 실선은 시계방향으로만 움직일 수 있다.

queue2.push(queue1[q1Index++]) 을 수행하면 아래와 같이 실선이 이동하며 큐는 아래와 같게 된다.

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

이것은 알고 있는 원리이다. 이 원리를 통해 최악의 경우를 구하고자 한다.

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

n을 입력받은 queue의 길이 라고 정의하면
이 때 총 이동거리는 2n-1 (붉은 선 이동거리) + n-2 (초록 선 이동거리). 즉, 3n-3이 된다.

따라서 최악의 경우는 3n-3이 된다.
즉, 두 개의 queue에 존재할 수 있는 모든 원소의 집합을 최대 3n-3번의 연산을 함으로써 만들 수 있다.

이렇게 감사하게도, 똑똑한 분의 글을 보고 이해를 할 수 있게 되었다.

let maxLen = (queue1.length + queue2.length) * 3 - 3;

따라서 위와 같은 코드까지의 순회를 하니 TC 1번이 통과가 되었다.

---

3️⃣ 느낀점

시간초과와 통과가 되지 않는 일부의 테스트 케이스가 가장 무서운 것 같다. 무엇이 문제인지 도무지 알 수가 없고 어디에 문제가 있는 지 찾기 힘들다.

그래도 스마트하고 스마트한 분 덕분에 왜 3n-3까지 생각해야 하는 지 알 수 있었다. 하지만, 2배까지해도 통과를 하고 +5까지만 해도 통과를 한다.
단지, 3n-3은 최악의 경우일 뿐이다. 최악의 경우까지 생각해서 나쁠 건 없는 것 같다. 물론, 문제를 풀 때는 통과할 때까지의 기준선을 마련하면 좋겠지만, 그 기준선이 최악의 경우를 넘어가진 않으니 문제를 해결하기 위해서 걸림돌이 되지는 않는다.

최악의 경우까지 생각해내는 똑똑이가 되기 위해 노력해보자❗️그럼 안녕핑🐌