23304_아카라카 최적화 C++

• 확실히 argument들에 대해 '참조' 여부를 명확히 하는 문법이 뭔가 편한 느낌이다.
• substr로 새로운 배열을 계속 복사하기보다는 idx를 가지고 계산하면 훨씬 효율적이다.

---

내 코드 vs 최적화 코드

• Memory : 15568KB vs 7796KB
• Time : 164ms vs 80ms

내 코드
#include <iostream>
#include <string>
#include <math.h>
using namespace std;

bool isPelindrom(string testString) {
    for (int i = 0; i < floor(testString.length() / 2); i++) {
        if (testString[i] != testString[testString.length() - i - 1]) {
            return false;
        }
    }
    return true;
}

bool checkPel(string strs) {
    // if baseCamp, return true
    if (strs.length() == 1) {
        return true;
    }

    int len = floor(strs.length() / 2);
    string front = strs.substr(0, len);
    string back = strs.substr(strs.length() - len, len);
    // floor(|S|/2) recursion fn call
    if (!checkPel(front) or !checkPel(back)) {
        return false;
    }

    // check 1st condition
    if (!isPelindrom(strs)) {
        return false;
    }

    // check 2nd condition
    if (!isPelindrom(front) or !isPelindrom(back)) {
        return false;
    }

    return true;
}

int main() {
    string S;
    cin >> S;

    cout << ((checkPel(S)) ? "AKARAKA" : "IPSELENTI");

    return 0;
}

최적화 코드
#include <bits/stdc++.h>
using namespace std;

bool isPal(const string &s, int l, int r) {
    while (l < r) if (s[l++] != s[r--]) return false;
    return true;
}

bool checkPel(const string &s, int l, int r) {
    if (l == r) return true;
    int len = (r - l + 1) / 2;
    int mid = l + len;
    if (!checkPel(s, l, mid - 1) || !checkPel(s, r - len + 1, r))
        return false;
    return isPal(s, l, r);
}

int main() {
    string S;
    cin >> S;
    cout << (checkPel(S, 0, S.size() - 1) ? "AKARAKA" : "IPSELENTI");
}