백준 1254번 [팰린드롬 만들기](C++) -yes6686- 티스토리

백준 문제 풀이: 1254 (팰린드롬 만들기)

---

문제 링크: https://www.acmicpc.net/problem/1254

문제 설명:

주어진 문자열을 팰린드롬(회문)으로 만들기 위해 문자열 뒤에 최소한의 문자를 추가합니다. 추가된 문자를 포함한 문자열의 최종 길이를 출력하세요.

---

문제 해결 코드

#include <iostream>
using namespace std;

// 문자열이 팰린드롬인지 확인
bool isPalin(const string &s) {
    for (int i = 0; i < s.size() / 2; i++) {
        if (s[i] != s[s.size() - i - 1]) {
            return false;
        }
    }
    return true;
}

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

    string s;
    cin >> s;

    int n = s.size();
    for (int i = 0; i < n; i++) {
        // s의 부분 문자열 s[i:]가 팰린드롬인지 확인
        if (isPalin(s.substr(i))) {
            cout << n + i << '\n'; // 팰린드롬을 만들기 위한 최종 길이 출력
            return 0;
        }
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 문자열의 뒤에서부터 점진적으로 팰린드롬 여부를 확인하며 최소한의 문자를 추가합니다.
• 구현 세부사항:
  • isPalin(): 주어진 문자열이 팰린드롬인지 확인하는 함수입니다.
  • s.substr(i): 문자열의 i번째부터 끝까지의 부분 문자열을 생성합니다.
  • i를 0부터 증가시키며, s.substr(i)가 팰린드롬인지 확인하고, 팰린드롬이면 현재 문자열 길이 n + i를 출력합니다.
• 시간 복잡도 분석:
  • 팰린드롬 여부 확인은 O(n)입니다.
  • 최대 n개의 부분 문자열을 확인하므로 최악의 경우 시간 복잡도는 O(n²)입니다.
  n의 최대값이 50이므로, O(n²) 풀이가 문제 없이 작동합니다.

---

결과

주어진 문자열에 최소한의 문자를 추가하여 팰린드롬을 만들기 위한 최종 문자열의 길이를 정확히 계산합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!