[프로그래머스/C언어] 연속 부분 수열

프로그래머스 코딩테스트 연습 문제 중, 연속 부분 수열 문제를 풀어보았다. 

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

프로그래머스

 

해당 문제는 주어진 수열이 끝과 처음이 다시 연결된 수열이라고 가정하고, 부분 수열의 합 중 중복되지 않는 것의 개수를 구하는 문제이다. 조금이라도 더 간단한 방법을 찾으려 했지만, 결국 모든 경우를 다 구하고 중복을 확인하는 수밖에 없다. 

그래도 합을 구하는 과정이라도 좀 더 간단하게 하고자, 크기가 n인 부분 수열의 합을 구하기 위해 크기가 n-1인 부분 수열의 합에 그다음 원소를 더해나가는 방식으로 모든 경우의 수를 구했다. 마지막으로 모든 경우의 수를 저장해놓은 수열을 qsort 함수로 오름차순으로 정렬하여, 중복된 숫자를 고려하지 않은 개수를 셌다.

 

solution을 보면, 크기가 1은 부분수열의 합을 구하는 것으로 시작한다. 크기가 1인 부분수열 원소들의 합은, 원소 그 자체이다. 따라서 원소들을 그대로 res 배열에 옮겨 담아 준다. 

다음 크기가 2인 부분 수열부터는 위에서 설명한 것과 같은 방식으로 수열의 합들을 구해준다. 앞서 이미 구해둔 크기가 n-1인 부분수열 원소들의 합에 그다음 원소를 하나만 더해주는 것이다. 그다음 원소의 인덱스는 idx이고, 크기가 n-1인 부분 수열 원소들의 합은 res 배열 내, pre_l부터 pre_r까지 저장되어 있다. 

이 과정을 반복하여, 크기가 element_len인 부분수열의 합까지 확인해주면, res 배열은 총 elements_len * elements_len 개의 원소를 가지게 된다. (즉, res_i = elements_len * elements_len) 이제 이 배열을 qsort 함수로 정렬해 준 후, 중복되지 않는 값의 개수를 answer에 카운트하여 리턴해준다. 

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

int compare(void* a, void* b) {
    return *((int*)a) - *((int*)b);
}

int solution(int elements[], size_t elements_len) {
    int* res = (int*)malloc(sizeof(int) * elements_len * elements_len);
    int res_i = 0;
    while (res_i < elements_len) {
        res[res_i] = elements[res_i];
        res_i++;
    }
    int pre_l = 0, pre_r = res_i;
    
    for (int i = 2; i <= elements_len; i++) {
        for (int j = 0; j < elements_len; j++) {
            int idx = j + i - 1;
            if (idx >= elements_len) idx -= elements_len;
            res[res_i++] = res[pre_l+j] + elements[idx];
        }
        pre_l = pre_r;
        pre_r = res_i;
    }
    
    qsort(res, res_i, sizeof(int), compare);
    int pre = res[0];
    int answer = 1;
    for (int i = 0; i < res_i; i++) {
        if (pre != res[i]) {
            answer++;
            pre = res[i];
        }
    }
    return answer;
}

 

 

여기서 qsort 함수는 비교적 최근에 알게 된 함수인데(그전까지 c언어에 sort를 담당하는 함수가 있는지 몰라서 직접 구현해서 사용하고 있었다... 이것 역시 low level 함수만 허용했던 42에서 공부했던 영향이기도 하다...), 사용법은 아래와 같다. 

qsort(배열, 배열의 길이, 배열 원소 하나 당 크기, 배열 두 개를 비교하는 함수)

 

원소는 int나 char 혹은 문자열까지 다양하게 들어갈 수 있다. 만약 문자열 여러 개를 sort하는 작업을 한다면 배열의 길이는 문자열이 몇 개인지, 배열 원소 하나당 크기는 문자열의 길이가 될 것이다.