[프로그래머스] 두 큐 합 같게 만들기

ynoolee·2022년 8월 25일
0

코테준비

목록 보기
132/146

https://school.programmers.co.kr/learn/courses/30/lessons/118667

문제

문제 이해

  • 길이가 같은 두 개의 queue
  • 하나의 queue (pop) -> 다른 queue (insert)
    • 목적: 각 큐의 원소 합이 서로 같도록 한다.
  • 구해야 하는 것 : 필요한 작업의 "최소 횟수"
    • 작업 1번 : pop + insert
  • 문제에서는 큐를 "배열"로 표현한다 -> 작은 index 일 수록 먼저 집어넣은 것
  • 두 개의 큐가 주어지면
    • 각 큐의 원소의 합이 되어야 하는 값 : 두 큐의 모든 원소의 합 / 2

문제 풀이

일단 첫 번째 생각은 틀렸었다 ㅋㅋ...
이래서 예시까지 모두 읽어보고 풀이를 시작해야하는 것 같다

나는 고정된 큐만을 생각하고 있었다. 그래서 " 맨 처음의 큐의 상태" 를 기반으로 누적합을 사용하는 것을 생각했었다.
그리고, insert, pop 이후 두 큐의 길이가 같아야 한다고도 생각하고 있었다... (아님)

그런데 이렇게 하면, 동적으로 변하는 큐를 고려하지 않게 되는 문제가 존재한다.

   [1,2,1,2]
[1,10,1,2] 가 있는 경우 -> 총합 : 6 + 11 + 3 = 20 이다

->
[] 다(4) pop 해서 q2 에 insert
[1,10,1,2,1,2,1,2]
->
[1] q2 에서 하나 pop 해 옴 (5)
[10,1,2,1,2,1,2]
->
[1,10] q2 에서 하나 Pop 해옴 (6)
[1,2,1,1,2,1,2]
->
[10] q2 로 하나 insert 함 (7)
[1,2,1,1,2,1,2,1]

문제 풀이 변경

  • q1, q2 를 이어 붙여, 합이 2/A 인 특정 수열을 구하는 것으로 생각해 봐야 한다.
    • 그런데 이걸 어떻게 구해야하는 건지 생각이 안났다.. idx 가 0인 때부터 차례차례 다 해봐야 하나 생각했다. 이렇게 하면 30만 x 30만 가지 경우의 수가 나와서 시간초과가 나올 것이 분명하다.
    • 분명 이런 상황('\~ 인 것을 구하기')과 비슷한 문제를 예전에 풀어 본 기억이 있었다 -> 투 포인터를 사용해 보자~~
    • 아... 생각해보니, 투 포인터를 할 경우, sum 이 특정값인 경우도 많이 존재한다. 각 경우들에서 최소횟수를 만들어내는 경우를 또 찾아내야한다 ㅠㅠㅠ..
    • 심지어 투 포인터에서도 , sum 이 A/2 인 여러 경우들을 찾는 것을 고려해야하는데, 이러면 또 경우의수 (left 를 움직이냐 right 를 움직이냐) 가 엄청 많아진다.. 이렇게 푸는 것은 아닌 것 같다.
  • 동적으로 변경되는 것 까지 모두 고려 되기 위해서는, 직접 push pop 해보는 것 밖에 없는 거 아닐까..???
    - 복잡하게 생각한 것이 문제인 것 같기도 하다.

두 큐의 총합을 구해 이것을 A 라고 칭한다.

“최소 횟수" 라는 것이 걸렸었는데

어차피 A/2 보다 작으면 원소를 받아야지만 A/2 가 될 수 있다.

어차피 A/2 보다 크면 원소를 보내줘야 한다.

그리고 이 문제는 queue 라서 한 곳으로만 빼고, 한 곳으로만 받을 수 있어서, 그냥 A/2 보다 작으면 추가하고, 크면 빼는 식으로 생각해도 될 문제였다.

즉, Greedy 문제였다.

실제 Queue 에서 넣었다 뺐다 하기엔 뭔가 불안해서

위에서 생각했던 것 처럼 q1, q2 를 이어 붙여 사용하는 것으로 생각했다.

그리고 index 만을 사용하는 것이다. → 하나의 거대한 circular queue 처럼 생각하면 된다.

따라서 아래와 같이 하면 될 것 같다.

q1 에는 f1(front), r1(rear) 포인터를 갖고

q2 는 f2(front), r2(rear) 포인터를 갖는다

q1 을 기준으로만 한다.

  • q1 이 A/2 보다 더 작은 경우
    • r1 = (r1+1)%len
    • f2 = (f2+1)%len
  • q2 이 A/2 보다 더 큰 경우
    • f1 = (f1+1)%len
    • r2 = (r2+1)%len

하지만 이 경우, 불가능한 경우에는 “무한 반복" 을 하게 되기 때문에 “횟수 제한" 을 둬야 한다.

  • 💥 개인적으로 “횟수제한" 에서 막혔었다…. → 이거를 제대로 안하면 case 1 에서 계속 실패하게 된다.

나는 각 큐 모두 한 번씩 다 이동된 횟수 → 즉, q1.len*2 면 충분하다고 생각했었다.

그런데 다음과 같은 경우가 존재한다. (🐳 반례의 중요성..!!)

따라서 q.len*3 까지만 반복하도록 한다.

이 “반복 횟수" 는 무한 루프를 돌아서 시간초과가 나는 것을 방지하는 용도 이기 때문에, 일정 수 이상의 값으로만 limit 을 주면돼서, 사실 명확하게 q.len*3 이 아닐 수도 있다. 이보다 작은 값의 limit 일 수도 있음.

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = -2;

        int len = queue1.length + queue2.length;

        int[] total = concatenate(queue1,queue2,len);

        long s1 = sum(queue1);
        long s = sum(total);

        if(s % 2 != 0) { // 총 합이 홀 수라면 두 큐의 합이 같아 질 수 없다
            return -1;
        }

        answer = search(total, 0, queue1.length, queue1.length-1, len-1, s/2, s1);

        return answer;
    }

    // 두 큐 를 길게 이어 붙인 결과를 리턴한다
    private int[] concatenate(int[] q1, int[] q2, int len) {
        int[] total = new int[len];

        for(int i =0; i< q1.length; i++) {
            total[i] = q1[i];
            total[q1.length + i] = q2[i];
        }

        return total;
    }

    private int search(int[] arr, int front1, int front2, int rear1, int rear2, long target, long curSum) {
        int f1 = front1;    int f2 = front2;
        int r1 = rear1;     int r2 = rear2;
        long s = curSum;
        int len = arr.length; // 작업 횟수는 len 미만이어야 한다.
        int cnt = 0;
        boolean fail = true;

        while(cnt <= (len + len / 2)) {
            if(s == target) {
                fail = false;
                break;
            }
            else if ( s < target ) {
                r1 = (r1 + 1) % len;
                f2 = (f2 + 1) % len;
                s += arr[r1];
                cnt++;
            } else {
                s -= arr[f1];
                f1 = (f1 + 1) % len;
                r2 = (r2 + 1) % len;
                cnt++;
            }
        }

        if(fail) return -1;

        return cnt;
    }

    private long sum(int[] arr) {
        int len = arr.length; 
        long sum = 0;

        for (long numb : arr) {
            sum += numb;
        }

        return  sum;
    }
}

0개의 댓글