[C++로 풀이] 가장 긴 팰린드롬⭐⭐⭐

📌 가장 긴 팰린드롬

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이 ⭕

• 팰린 드롬의 종류는 두 가지가 있다.
  • 1️⃣ caabaac처럼 가운데 하나가 중심이 되어 이걸 기준으로 양 옆이 동일.
    • 가운데 b를 중점으로 caabaac, caabaac, caabaac 이렇게 좌우가 같다.
  • 2️⃣ baab처럼 가운데 하나가 중심이 되는 것은 아니고, 그냥 양 옆이 동일.
    • aab, aabb 이렇게!

이렇게 두 가지 종류가 있다고 판단하고 코드를 짰다.

✈ 1 차 풀이 (⏰ 효율성 테스트 2번에서 시간 초과)

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(string s)
{
    int answer = 0; 
    // caabaac
    for (int center = 1; center < s.length() - 1; center++) {
        string temp(1, s[center]);
        for (int left = center - 1, right = center + 1; left >= 0, right < s.length(); left--, right++) {
            if (s[left] != s[right]) break;
            temp = s[left] + temp + s[right];
        }
        answer = max(answer, (int)temp.length());
    }
    // baab
    for (int center = 0; center < s.length() - 1; center++) {
        string temp = "";
        for (int left = center, right = center + 1; left >= 0, right < s.length(); left--, right++) {
            if (s[left] != s[right]) break;
            temp = s[left] + temp + s[right];
        }
        answer = max(answer, (int)temp.length());
    }

    return answer;
}

• 1️⃣ aabaa
  • center는 하나의 중점이 될 문자의 인덱스를 뜻한다. center는 1부터 시작하여 1,2,3 이 될 수 있다. 즉 위 문자열에서 중점이 될 수 있는건 가운데 aabaa 부분이다.
  • 현재의 center를 중점으로, 중점의 왼쪽에 있는 원소와 오른쪽에 있는 원소가 같은지를 비교하고 같다면 팰린드롬을 완성해나간다.
  • left 혹은 right 둘 중 하나라도 끝에 도달했거나 더 이상 팰린드롬이 되지 않는다면 해당 center의 팰린드롬 구하기는 종료하고 다음 원소를 center로 하러 가야됨.
    • “abcdcba” 에서 현재 center가 2 라면 (즉 c 가 현재 중점 원소라면) b와 d를 비교 한다. 이 경우 b와 d는 다르기 때문에 종료 한다. 그래서 중점이 c일 땐 팰린드롬은 "c" 달랑 한개가 끝이다.
    • “abcdcba” 에서 현재 center가 3 라면 (즉 d 가 현재 중점 원소라면)
      • c와 c는 같다. -> 팰린드롬 = “cdc”
      • b와 b는 같다. -> 팰린드롬 = “bcdcb”
      • a와 a는 같다. -> 팰린드롬 = “abcdcba”
      • 따라서 d가 중점일 땐 가장 긴 팰린드롬이 “abcdcba”가 된다.
• 2️⃣ baab
  • baab -> baab -> baab 이 순서로 비교해나간다.
  • 따라서 이땐 center는 0부터 시작 하고(b,a,a 까지가 center가 될 수 있음) left는 딱 center에서 시작하여 감소, right는 center + 1에서 시작하여 증가하는 식으로 함.
    • “baab” 에서 현재 center가 1이라면
      • a와 a는 같다. -> 팰린드롬 = “aa”
      • b와 b는 같다. -> 팰린드롬 = “baab”
      • 따라서 center가 1일 땐 가장 긴 팰린드롬이 “baab”가 된다.
• 이렇게 각각의 경우마다 가장 긴 팰린드롬 문자열을 구하고 최종적인 최대 길이 값을 업뎃해 나간다.

근데 위 코드는 시간 초과가 발생한다. 내가 각각의 center에서의 팰린드롬을 temp 문자열에 직접 만들어서 업뎃하고 그 길이를 구하는 식으로 코드를 짰는데 사실 문제에서 원하는건 팰린드롬 문자열이 아닌 팰린드롬 문자열의 "길이"이므로 그냥 길이만 업뎃하면 됐었다. 문자열 접합 연산이 시간이 꽤 소모가 많이 드는 작업인 듯하다.

✈ 2 차 풀이 ⭕

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(string s)
{
    int answer = 0;
    // aabaa
    for (int center = 1; center < s.length() - 1; center++) {
        int t_max = 1;
        for (int left = center - 1, right = center + 1; left >= 0, right < s.length(); left--, right++) {
            if (s[left] != s[right]) break;
            t_max += 2;
        }
        answer = max(answer, t_max);
    }
    // aabb
    for (int center = 0; center < s.length() - 1; center++) {
        int t_max = 0;
        for (int left = center, right = center + 1; left >= 0, right < s.length(); left--, right++) {
            if (s[left] != s[right]) break;
            t_max += 2;
        }
        answer = max(answer, t_max);
    }

    return answer;
}

따라서 위와 같이 코드를 바꿨고 시간 초과 문제를 해결하였다.

int t_max = 1;
t_max += 2;

int t_max = 0;
t_max += 2;

• 팰린드롬 발견시마다 2 씩만 더해주면 된다.
  • 1️⃣ aabaa 👉 초기값 1 (중점이 되는 하나가 있을 때의 가장 짧은 팰린드롬 길이는 1이다.)
    • 1 에서 2 씩 더해나가니 홀수 길이다.
  • 2️⃣ baab 👉 초기값 0 (모두 다 짝지어져 있는 형태의 팰린드롬 중 가장 짧은 길이는 0이다. 사실 0 이면 팰린드롬이 아니라는거긴 하지만..)
    • 0 에서 2 씩 더해나가니 짝수 길이다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기