[백준 1213 C++] 팰린드롬 만들기

구현이 약해서 구현문제를 풀다가 시간복잡도에 대해 깊은 깨달음을 얻게 된 문제가 있어 풀이를 비교해보고자 한다.
문제는 만들 수 있는 회문을 파악해 만들 수 있는 경우 팰린드롬 결과를, 불가능하다면 "I'm Sorry Hansoo\n" 를 출력하는 문제이다.

모든 경우의 수를 조사한 시간복잡도가 매우 큰 코드

최근에 next_permutation 코드를 배워서 이를 활용하면 되겠다 생각하고 작성한 코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

string str;
vector<char> arr;

bool isPal(vector<char> a) {
  vector<char> tmp = a;

  reverse(tmp.begin(), tmp.end());
  
  if (tmp == a) {
    return true;
  } else {
    return false;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);

  cin >> str;

  for (char c : str) {
    arr.push_back(c);
  }

  do {
    if (!isPal(arr)) {
      continue;
    } else { 
      for (auto a : arr) {
        cout << a;
      }
      cout << '\n';
     }
  } while (next_permutation(arr.begin(), arr.end()));
}

이 코드는 주어진 문자열로 만들 수 있는 모-든 경우를 다 조사하고 이 중에 팰린드롬이 있다면 반환하는 형식이었다.

빌드는 정상적으로 됐기 때문에 제출했고, 시간초과가 떴다.

코드를 분석해보았다.
내가 작성한 코드의 시간복잡도는 O(n^2⋅n!) 이어서 n이 9만 넘어가도 요구되는 시간을 초과했으며, 50이 되는 경우 10^59이 넘는 시간이 걸린다.

문자열을 활용한 코드

#include <bits/stdc++.h>
using namespace std;

char mid;
int flag; // 홀수 갯수 체크하는 플래그 
string ret;

int main() {

  ios::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);

  vector<int> cnt(26, 0);
  string str;
  cin >> str;

  for (char c : str) {
    cnt[c-'A']++;
  }

  for (int i = cnt.size() - 1; i >= 0; i--) {
    if (cnt[i]) {
      // cout << "(char)i: " << (char)i << endl;
      // cout << "cnt[i]: " << cnt[i] << endl;

      if (cnt[i] & 1) {
        mid = (char)(i+'A');
        flag++;
        cnt[i]--;
      }
      if (flag == 2) {
        cout << "I'm Sorry Hansoo\n";
        return 0;
      }
      for (int j = 0; j < cnt[i]; j += 2) {
        ret = (char)(i+'A') + ret;
        ret += (char)(i+'A');
      }
    } 
  }
  if (mid) {
    ret.insert(ret.begin() + ret.size() / 2, mid);
  }
  cout << ret << '\n';

}

• vector 문자열을 선언해 26개의 배열에 각 코드에 해당하는 cnt 를 저장하도록 하면 개수 파악이 쉽다.
• 문자열 앞뒤로 각 문자를 붙이고, 가장 마지막에 mid가 있다면 이 때 가운데에 넣어준다.

이렇게 풀 경우, 시간복잡도는 O(n)으로 매우 효율적으로 동작할 수 있다.

코드를 작성하기 전에, 주어지는 입력데이터의 크기와 주어진 시간 안에 해결이 가능할지 미리 생각하는 습관을 들여야겠다.