[프로그래머스_ 자바스크립트] Lv.2 두 큐 합 같게 만들기 / 투포인터

 

[Javascript_ 두 큐 합 같게 만들기]

 

프로그래머스

 

---

 

<STUDY>

 

📢 문제

 

길이가 같은 두 개의 큐가 주어집니다.

하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다.

이때 필요한 작업의 최소 횟수를 구하고자 합니다.

한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.

 

큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며,

원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다.

즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다.

 

길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다.

각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요.

단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.

 

제한사항

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

 

---

 

<전체 코드>

 

function solution(queue1, queue2) {
    let arr = queue1.concat(queue2);
    let sum = arr.reduce((sum, v) => sum + v, 0);
    let sum1 = queue1.reduce((sum, v) => sum + v, 0);
    
    if (sum % 2 === 1) return -1;
    
    const half = sum / 2;
    let pointer1 = 0, pointer2 = queue1.length - 1;
    
    let count = 0;
    while (count <= arr.length * 3) {
        if (sum1 > half) sum1 -= arr[pointer1++ % arr.length];
        else if (sum1 < half) sum1 += arr[++pointer2 % arr.length];
        else return count;
        
        count++;
    }
    
    return -1;
}

 

 

---

 

두 queue를 합쳐서 합이 같아지는 부분이 앞쪽에서 먼저 나오면 될 것이라는 생각으로 문제에 접근했다.

 

그런데 투포인터를 사용할 생각을 하지 못해서 반복문만 계속 사용하는 과정에서 시간이 매우 오래걸렸다.

 

투포인터를 사용하고 나서는 pop과 insert로 인해 queue의 숫자가 계속 움직인다는 것을 생각하지 못하고 포인터 1과 포인터 2의 순서가 무조건 같아야 한다고 생각했다.

 

while (pointer1 <= pointer2) {
    if (sum1 > half) sum1 -= arr[pointer1++];
    else if (sum1 < half) sum1 += arr[++pointer2];
    else return count;
    
    count++;
}

 

그래서 처음에는 이런 식으로 코드를 작성했는데 테스트 케이스 2개가 자꾸 실패가 떴다.

 

이유는 두 개의 포인터의 순서가 바뀔 수도 있었기 때문이었고

이에 따라 두 queue를 합친 배열의 길이로 나눈 나머지 자리의 값을 더하고 빼는 과정이 필요했다.

 

---

 

조금만 더 깊이 생각했으면 풀 수 있는 문제였던 것 같은데 조금 아쉬웠다.

 

분발해야지 으쟈으쟈

 

---

🔆프로그래머스 Lv.2 두 큐 합 같게 만들기🔆

 

 

👉ez1n github 구경하기👈

 

ez1n - Overview