99클럽 코테 스터디 8일차 TIL [프로그래머스] 두 큐 합 같게 만들기

💡문제

[level 2] 두 큐 합 같게 만들기 - 118667

문제 링크

성능 요약

메모리: 131 MB, 시간: 27.82 ms

 

 

---

🤔접근법

문제 요약

• 배열의 형태로 주어진 두 큐의 합을 동일하게 만들었을 때 최소가 되는 이동 횟수를 출력

범위 체크 및 시간복잡도 예상

• 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
• 1 ≤ queue1의 원소, queue2의 원소 ≤ 10
• $O(queue)$

풀이법

❌ 접근 방법. 완탐

두 배열의 길이의 합이 8이라고 했을 때 두 배열로 나눌 수 있는 길이의 경우의 수는 아래와 같다

1 : 7 → 8경우

2 : 6 → 8경우

3 : 5 → 8경우

4 : 4 → 4경우 (1,2,3,4), (4,5,6,7) 이나 (4,5,6,7) , (1,2,3,4)은 같은 경우이기 때문

n으로 잡았을 때 N*N/2만큼의 시간복잡도를 가지게 된다.

여기서 n의 길이는 두 배열의 길이의 합이니 최대 600,000을 가지게 되어 터지게 된다.

완탐은 불가다 더 효율적인 방법을 찾아야한다

➡️ 해당 풀이법의 시간 복잡도 : $O(N *(N/2))$ → 시간 초과

 

 

 

⭕ 접근 방법. 완탐 + 최적화

두 큐의 관계로 봤을 때 하나의 원형큐라는 생각이 들었다.

두 큐를 하나의 배열로 만들어 큐를 시작하는 포인터를 두고 포인터를 움직이면 더 유용할 것이라는 생각이 들었고, 두 큐의 합은 매번 새로 합하지 말고 합을 담는 변수를 두고 원소가 빠져나가거나 더해질때마다 합계에서 그 원소만큼 더하고 빼는 방법을 선택하였다.

🔑 두 큐의 합계를 비교하여 합계가 큰놈이 작은놈에게 원소를 넘겨주자.

위 키포인트가 풀이의 전부이다.

두 큐의 합계를 비교해서 합계가 큰 큐에서 pop 하고 작은 큐로 push 한다.

물론 나는 하나의 배열을 이용했기 때문에 큐의 pop이나 push를 사용하지 않고 합계가 큰놈의 start 인덱스를 한칸 증가시켜 주었다.

그러면 배열의 앞머리는 한칸 줄어들고 다음 배열의 꼬리로 들어가기 때문이다.

만약 큐1의 합이 계속 작아서 큐2의 포이터를 계속 증가 시킨 후 두 포인터가 같아진다면 절대 합계를 동일하게 나눌 수 없는 경우임으로 break 조건을 추가한다.

🔑 start 포인터가 다시 제자리로 돌아오면 break;

위 break 조건은 쉽게 생각했지만 지금 break 조건은 쉽게 생각하지 못하였다.

반례를 추가한다

queue1 = [ 10, 5, 1 ]

queue2 = [ 2, 2, 2]

나는 두 start 포인터 중 하나라도 한바퀴를 돌아 다시 자리로 돌아오게 되면 나눠 볼수 있는 모든 경우를 다 봤다고 생각하고 break 해주었다.

(근데 이게 통과 했는데 생각해 보니까 두 포인터가 모두 돌아오는 경우를 봐야하지 않을까 싶은데…)

➡️ 해당 풀이법의 시간 복잡도 : $O(2*(두 큐 길이 합)) = O(4N)$

 

 

 

---

😎SUCCESS

고냥 단박에 성공

단박에 성공하지 못한 이유는 ?

• 두 큐의 합계가 int 범위가 넘어간다는걸 알려줬음에도 불구하고 고려하지 못하였다
• 멍청이 ..
• 두 큐의 start 포인터가 같아지는 경우 말고도 합계가 같아질 수 없는 경우가 있다는 것을 생각 못하였다.

---

👩‍💻 코드

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int len = queue1.length;

        int[] queue = new int[len *2];
        long sum1 = 0;
        long sum2 = 0;

        for (int i = 0; i < len; i++) {
            // queue1 + queue2 형태로 배열 합치기
            queue[i] = queue1[i];
            queue[i + len] = queue2[i];

            // queue1 과 queue2 합계 구하기
            sum1 += queue1[i];
            sum2 += queue2[i];
        }

        int answer = 0;
        int start1 = 0;
        int start2 = len;
        boolean isFirst1 = true; // start들이 돌아서 제자리로 돌아오면 같아질수 없는 경우이며 이를 체크하기 위한 boolean 값
        boolean isFirst2 = true;
        while (start1 != start2){
            if((!isFirst1 && start1 == 0) || (!isFirst2 && start2 == len)){
                answer = -1;
                break;
            }
            if(sum1 < sum2){ // queue2에서 빼서 queue1으로 넣기 -> start2을 오른쪽으로 이동
                sum2 -= queue[start2];
                sum1 += queue[start2];
                // start2 다음이 없다면 맨 앞으로 이동
                if(start2+1 == queue.length){
                    start2 = 0;
                }else{
                    start2++;
                    isFirst2 = false;
                }

            }else if(sum1 > sum2){ // queue1에서 빼서 queue2으로 넣기 -> start1을 오른쪽으로 이동
                sum1 -= queue[start1];
                sum2 += queue[start1];
                // start1 다음이 없다면 맨 앞으로 이동
                if(start1+1 == queue.length){
                    start1 = 0;
                }else{
                    start1++;
                    isFirst1 = false;  
                }

            }else{ // sum1 == sum2
                break;
            }
            answer++;
        }

        if(sum1 != sum2){
            answer = -1;
        }

        return answer;
    }
}