프로그래머스 Level 2 : 두 큐 합 같게 만들기 C언어

▶문제 : 코딩테스트 연습 - 두 큐 합 같게 만들기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

▶코드 작성

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int *q1, *q2;
int q1_len, q2_len;

long long calculation(int arrNum) { //arrNum값에 따른 큐의 원소 반환
    if (arrNum < q1_len) { //queue1
        return q1[arrNum];
    }
    else if (arrNum < q1_len + q2_len) { //queue2
        return q2[arrNum - q1_len];
    }
}

int solution(int queue1[], size_t queue1_len, int queue2[], size_t queue2_len) {
    long long half = 0;
    for (int i = 0; i < queue1_len; i++) half += queue1[i];
    for (int i = 0; i < queue2_len; i++) half += queue2[i];
    half /= 2; //절반값 구하기

    long long sum = queue1[0];
    int right = 0, left = 0;
    int count = 600000;
    q1 = queue1; q2 = queue2;
    q1_len = queue1_len; q2_len = queue2_len;

    while (true) {
        if (sum < half) { //절반값보다 작을 때
            right++;
            sum += calculation(right); //다음원소 추가
        }
        else if (sum > half) { //절반값보다 클 때
            if (right == left) { //하나의 원소만 있으므로 다음 원소로 이동
                right++;
                left++;
                sum = calculation(left);
            }
            else {
                left++;
                sum -= calculation(left - 1); //이전원소 제거
            }
        }
        else if (sum == half) { //절반값을 찾았을 때
            int m = 0;
            if (left < queue1_len && right < queue1_len) { //queue1안에서만 존재할 때
                m += left;
                if (right < queue1_len - 1) { //queue1안 범위에서 오른쪽에 남은 원소가 있다면
                    m += right + 1;
                    m += queue2_len;
                }
            }
            else if (left < queue1_len && right < queue1_len + queue2_len) { //queue1, queue2 두 부분을 걸칠 때
                m += left;
                m += right - queue1_len + 1;
            }
            else { //queue2안에서만 존재할 때
                m += left - queue1_len;
                if (right < queue1_len + queue2_len - 1) { //queue2안 범위에서 오른쪽에 남은 원소가 있다면
                    m += right - queue1_len + 1;
                    m += queue1_len;
                }
            }

            if (count > m) count = m; //최소횟수
            right++;
            sum += calculation(right); //다음원소 추가
        }

        if (right >= queue1_len + queue2_len) { //한바퀴를 다 돌았을 때
            if (count == 600000) return -1; //각 큐의 원소 합을 같게 만들 수 없음
            return count;  //최소횟수
        }
    }
}

 

▶해석

큐를 구현해 insert와 pop을 이용하여 풀면 비교적 쉽게 풀리겠지만 고려할 부분이 많다는 생각과 부족한 실력으로 다른 방법을 생각하였다.

 

변수 half에 큐의 전체 합의 절반값을 구하였다.

while문은 크게 3가지로 나뉘는데 sum이 half보다 작거나 크거나 같을 때이다.

여기서 sum을 구하는 방식은 sum이 half보다 작으면 오른쪽으로 이동하여 값을 더하고, half보다 크면 왼쪽 값을 빼준다.

예제 1을 예로 들면 queue1 : [3, 2, 7, 2] , queue2 : [4, 6, 5, 1] , half = 15

[3, 2, 7, 2] [4, 6, 5, 1] : 첫 시작은 queue1의 맨 왼쪽 원소부터 시작한다. sum : 3

[3, 2, 7, 2] [4, 6, 5, 1] : half보다 sum이 작으므로 오른쪽으로 이동하여 값을 더해준다. sum : 5

[3, 2, 7, 2] [4, 6, 5, 1] : half보다 작으므로 오른쪽 값을 더한다. sum : 12

[3, 2, 7, 2] [4, 6, 5, 1] : half보다 작으므로 오른쪽 값을 더한다. sum : 14

[3, 2, 7, 2] [4, 6, 5, 1] : half보다 작으므로 오른쪽 값을 더한다. 이때 right의 계산은 calculation함수가 해주어 queue2 [0]이 되도록 만들어준다. sum : 18

[3, 2, 7, 2] [4, 6, 5, 1] : half보다 크므로 왼쪽 값을 빼준다. sum : 15

sum==half 이므로 pop과 insert의 횟수를 구한다. 구하는 방식은 아래에 있다. count : 2

[3, 2, 7, 2] [4, 6, 5, 1] : 다른 경우의 수가 있을 수 있으므로 오른쪽 값을 더한다. sum : 21

[3, 2, 7, 2] [4, 6, 5, 1] : half보다 크므로 왼쪽 값을 빼준다. sum : 19

[3, 2, 7, 2] [4, 6, 5, 1] : half보다 크므로 왼쪽 값을 빼준다. sum : 12

[3, 2, 7, 2] [4, 6, 5, 1] : half보다 작으므로 오른쪽 값을 더한다. sum : 17

[3, 2, 7, 2] [4, 6, 5, 1] : half보다 크므로 왼쪽 값을 빼준다. sum : 15

sum==half 이므로 pop과 insert의 횟수를 구한다. 7번이 나오는데 기존의 count보다 많으므로 넘어간다.

[3, 2, 7, 2] [4, 6, 5, 1] : 다시 다른 경우의 수가 있을 수 있으므로 오른쪽 값을 더한다. sum : 16

[3, 2, 7, 2] [4, 6, 5, 1] : half보다 크므로 왼쪽 값을 빼준다. sum : 12

더 이상 오른쪽으로 넘어갈 수 없으므로 count값을 확인한다.

count값이 처음 대입한 600000이라면 양쪽 큐의 값을 같게 만들 수 없다는 의미이므로 -1을 반환한다.

아니면 count값에 들어간 최소 횟수를 반환한다.

 

sum==half 일 때도 크게 3가지로 나뉘는데 범위가 queue1안에 있을 때, queue1과 queue2 둘 다 있을 때, queue2안에 있을 때이다.

queue1안에 있을 때와 queue2안에 있을 때는 방식이 같다.

예를 들어 [1, 2, 2] [1, 1, 1] 노란색만 queue1에 남기기 위해 1을 pop 하여 queue2에 insert 하면 횟수는 1이다.

따라서 노란색을 제외한 왼쪽 값들의 개수를 세면 횟수를 구할 수 있다.

하지만 예제 2를 보면 [1, 2, 1, 2] [1, 10, 1, 2] 노란색의 오른쪽에 값이 있어 다음 과정을 거쳐야 한다.

[1, 2, 1, 2, 1, 10] [1, 2] : 10 혼자 남기기 위해 queue1로 insert 하여 현재 횟수 : 2

[10] [1, 2, 1, 2, 1, 2, 1] : 10 앞에 있는 수들을 queue2로 insert 하여 최종 횟수 : 7

 

queue1과 queue2 둘 다 있을 때는 쉽다. 위의 예제 1을 보면 [3, 2, 7, 2] [4, 6, 5, 1]

[3, 2, 7, 2, 4] [6, 5, 1] : 4를 queue1로 insert 하여 현재 횟수 : 1

[2, 7, 2, 4] [6, 5, 1, 3] : 3을 queue2로 insert 하여 최종 횟수 : 2

 

이 코드는 정말 어떻게든 풀고 싶을 때 억지로 짠 거 같은 느낌이 든다... 더욱 간단하고 쉬운 방법이 분명 있을 것이다.