프로그래머스 두 큐 합 같게 만들기(투 포인터)

제목에 큐가 들어가서 큐 문제인 줄 알았는데 .. 예전에 잠깐 스치듯이 공부한 슬라이딩 윈도우 옆에 있던 놈이 문득 생각나서 찾아서 풀어봤다...

어제까지 끙끙대다가 포기할까 했는데 저 킹받는 점 세개를 도저히 참을 수 없었다.

 

투 포인터란?

1차원 배열이나 리스트에서 특정 조건을 만족하는 부분을 찾거나, 두 요소 간의 관계를 조사하는 데 사용되는 알고리즘 기법이다.

슬라이딩 윈도우와 구분되는 점은, 윈도우 사이즈가 필요에 따라 변할 수 있다.

그리고 투 포인터는 양 방향으로 이동이 가능하지만 슬라이딩 윈도우는 한 방향으로밖에 이동하지 못한다.

이 문제에서 내가 투 포인터를 쓰고자 한 이유는, 두 개의 1차원 배열을 같은 값으로 만들어야 하기에
queue1과 queue2의 시작방향을 두 포인터의 시작지점으로 설정하고

queue1과 queue2원소를 모두 합한 값의 절반값과 비교하며 어떤 포인터를 이동시킬지 정할 수 있기 때문이다.

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

// queue1_len은 배열 queue1의 길이입니다.
// queue2_len은 배열 queue2의 길이입니다.
int solution(int queue1[], size_t queue1_len, int queue2[], size_t queue2_len) {
    int answer = 0;
    int sum1 = 0;
    int sum2 = 0;
    for(size_t i = 0; i < queue1_len; i++) sum1 += queue1[i];
    for(size_t i = 0; i < queue2_len; i++) sum2 += queue2[i];
    int total = sum1 + sum2;
    if(total % 2 == 1) return -1; //토탈이 홀수면 반반 못나눔
    int num = total / 2;
    
    // queue1 start1, queue2 start2. 
    // num과 sum1 or sum2 중 더 큰 값에서 하나씩 빼서 더 작은 쪽에 넣음 > 반복.
    // start1을 0, start2를 0으로 시작해서 .. sum1과 sum2와 num 비교하고, 더 작은 쪽에 queue1[start1] 넣기 ?
    printf("%d %d\n", sum1, sum2);
        
    int start1 = 0;
    int start2 = 0;
    int count = 0;
    while(start1 < queue1_len * 2 && start2 < queue2_len){
        printf("%d %d\n", sum1, sum2);
        if(sum1 == num && sum2 == num){
            answer = count;
        }
        else if(sum1 > num){
            sum2 += queue1[start1];
            sum1 -= queue1[start1];
            count++;
            start1++;
        }else if(sum1 < num){
            sum1 += queue2[start2];
            sum2 -= queue2[start2];
            count++;
            start2++;
        }else return -1; 
    }
    answer = count;
    return answer;
}

처음 작성 한 코드.

근데 코드를 다 쓰고 실행 버튼을 누르고 깨달았다. 뭐 일단 무한루프에도 빠지고 난리가 났다.

흠.......................... .........................................

.........

로그를 보고 해답을 찾았다. start로 그대로 나눠버리면, start가 queue1_len과 같거나 클 때 문제가 발생한다.
때문에, 나머지 연산자를 활용해서 start와 end를 queue_len으로 나누었다.

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

// queue1_len은 배열 queue1의 길이입니다.
// queue2_len은 배열 queue2의 길이입니다.
int solution(int queue1[], size_t queue1_len, int queue2[], size_t queue2_len) {
    int sum1 = 0;
    int sum2 = 0;
    for(size_t i = 0; i < queue1_len; i++) sum1 += queue1[i];
    for(size_t i = 0; i < queue2_len; i++) sum2 += queue2[i];
    int total = sum1 + sum2;
    if(total % 2 == 1) return -1; //토탈이 홀수면 반반 못나눔
    int num = total / 2;

    int start = 0;
    int answer = 0;
    int end = queue1_len;
    int limit = queue1_len * 2 + queue2_len * 2;
    
    while(answer <= limit){ //limit 초과된 answer값이 나올 수 없음
        if(sum1 == num) return answer;  //같으면 바로 answer 리턴
        if(sum1 > num){
            sum1 -= queue1[start % queue1_len]; //num이 sum1보다 작은 경우 queue1[0]를 뺌
            start++;    //1에서 뺐으니 start 위치 이동 0 => 1,2,3,4...
        }else{
            sum1 += queue2[end % queue2_len];   //num이 sum1보다 큰 경우 queue2[0]를 더함
            end++;    //2에서 뺐으니 end(queue1의 길이와 같으나 나머지 연산법으로 0 => 1,2,3...) 위치 이동
        }
        answer++;
    }
    return -1;
}

개선한 코드. limit변수를 선언하고, start1,2를 start와 end로 나누어서 코드의 가독성을 전체적으로 높였다. 또한, 값을 비교하는 if 문에서 sum1만으로만 식을 쓰고, 불필요한 변수(count)와 반복되는 count++를 while문 맨 아래에 answer++로 대체했다.

하지만, 어떤 방법으로도 "원소 합을 같게 만들 수 없는 경우"에서 오류가 생겨서

printf("%d, %d, %d, %d, %d, %d\n", answer, sum1, start%queue1_len, end%queue2_len, start, end); 로 로그를 찍어봤다.

queue1[start % queue_len] 이, start가 만약 queue_len으로 깔끔하게 나누어 지는 수라면 값이 제대로 반영이 안 돼서 오류가 생긴 것 같다. end도 마찬가지로..
깔끔하게 나눠진다는 뜻은, queue1 길이와 같게 된다는 뜻이다.

즉 start나 end값이 queue1길이나 queue2길이와 같거나 큰 경우, 다른 큐로 넘기는 경우도 생각했어야 됐다.

나머지 연산자를 너무 무식하게 썼다... 왜 이 생각을 진작 못 했을까?

다른 문제에서 사용한 기법을 억지로 적용하려 한 게 문제다. ㅠㅠ

식을 쓸 땐 항상 근거를 생각하고 쓰자.

ㅇㅁㄹㅇ로먇져ㅗ랴ㅕㅈ도랴면ㄷ조랴ㅕㅁ도랴ㅕㅁㄷ롬풀었따!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

글로 쓰니 뚝딱 푼 것 처럼 보이는데, 6시간 걸렸다 푸하하하하하ㅏ하하하하핳

 

최종 코드는 이러하다.

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

// queue1_len은 배열 queue1의 길이입니다.
// queue2_len은 배열 queue2의 길이입니다.
int solution(int queue1[], size_t queue1_len, int queue2[], size_t queue2_len) {
    long long sum1 = 0;
    long long sum2 = 0;
    for(size_t i = 0; i < queue1_len; i++) sum1 += queue1[i];
    for(size_t i = 0; i < queue2_len; i++) sum2 += queue2[i];
    long long total = sum1 + sum2;
    if(total % 2 == 1) return -1;
    long long num = total / 2;

    int start = 0;
    int end = 0;
    int answer = 0;
    int limit = queue1_len * 2 + queue2_len * 2;
    
    while(answer <= limit){
        if(sum1 == num) return answer;
        if(sum1 > num && start >= queue1_len){
            sum1 -= queue2[start % queue1_len];
            start++;
        }else if(sum1 < num && end >= queue2_len){
            sum1 += queue1[end % queue2_len];
            end++;
        }else if(sum1 > num){
            sum1 -= queue1[start % queue1_len];
            start++;
        }else{
            sum1 += queue2[end % queue2_len];
            end++;
        }
        answer++;
    }
    return -1;
}

 

 

드디어 다른 공부를 할 수 있당!!!!!!!