[코드업 4434] 좋은 수열

해당 문제는 백트래킹 방식으로 연속된 부분수열을 포함하지 않는 수열을 만들어내는 문제이다. 생각해내는데 많은 시간이 들었고, 수열을 체크하는 함수 디버깅에 많은 시간이 소요됐다. 집중할 수 있는 환경을 만들고, 내 알고리즘을 먼저 의사코드로 만들어 낸 후 작업을 진행하는 훈련을 계속 진행해야한다. 아래는 정답 소스이다.

 

#include <iostream>
#include <string>

using namespace std;

string numbers[3] = {"1", "2", "3"};

bool checkSeries(const string& series) {

    bool result = true;
    int sizeIdx = 2;
    int firstIdx = 0;
    int seriesSize = series.size();

    if (seriesSize <= 2) return result;

    while (firstIdx <= seriesSize - 2) {

        string subset = series.substr(firstIdx, sizeIdx);
        string lastPart = series.substr(firstIdx + sizeIdx, -1);

        if (subset.size() > lastPart.size()) {
            sizeIdx = 1;
            firstIdx++;
            continue;
        }

        if (lastPart.find(subset) == 0) {
            result = false;
            break;
        }

        sizeIdx++;
        
        if (firstIdx + sizeIdx == seriesSize - 1) {
            sizeIdx = 1;
            firstIdx++;
        }
    }

    return result;
}

void makeNumbers(int N, string series, int lastChoose) {
    // 기저사례 : 수열을 다 만들었다면
    if (!checkSeries(series)) return;
    if (series.size() == N) {
        cout << series << endl;
        exit(0);
    }

    // 세 개의 숫자 중 하나 뽑기
    for (int idx = 0; idx < 3; idx++) {
        if (idx != lastChoose) {
            series.append(numbers[idx]);
            makeNumbers(N, series, idx);
            series = series.substr(0, series.size() - 1);
        }
    }
    
}

int main() {

    int N;
    cin >> N;

    string series = "";
    makeNumbers(N, series, -1);

    return 0;
}

 

중요한 부분은 수열을 체크하는 부분이다. 앞에서부터 수열을 쪼개면서 부분수열이 연속되어 있는지 확인하는 방식이다. 아이디어는 간단했지만 C++ substr 함수를 제대로 숙지하지 않았고, 예외 상황을 생각하는데 너무 많은 시간이 걸려버렸다. 계속 연습해야한다.