[프로그래머스 C++] 가장 긴 팰린드롬

[프로그래머스 C++] 가장 긴 팰린드롬

 

https://school.programmers.co.kr/learn/courses/30/lessons/12904

프로그래머스

---

 

 

해결전략

 

구현

 

 

글자 자리를 한칸씩 이동하며 글자 자리 기준으로 양옆을 검사한다.

 

ex. "abcdcba"

• a 자리 검사
• b 자리 검사
  • 홀수 가정:  b기준으로 양옆의 a, c가 같은지 검사. 같다면 계속해서 양옆으로 가면서 검사.
    • int left = i-1, right = i+1;
    • if (s[left] != s[right])
  • 짝수 가정:  b기준으로 왼쪽의 a 검사. 같다면 계속해서 양옆으로 가면서 검사.
    • int l = i - 1, r = i; 
    • if (s[l] != s[r])

---

 

 

정답코드

 

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

int solution(string s){ // 주어진 문자열 s에서 가장 긴 팰린드롬의 길이를 반환하는 함수
    int n = s.size(); 
    int answer = 1; // 가장 짧은 팰린드롬의 길이는 1이므로 기본값을 1로 설정
    
    for (int i = 1; i < n; i++) // 문자열의 각 문자를 중심으로 팰린드롬을 찾음
    {
        int cnt = 1; // 현재 중심 문자를 포함한 팰린드롬의 길이
        int left = i-1, right = i+1; // 중심 문자의 양쪽 인덱스
        while (0 <= left && right < n) // 양쪽으로 탐색할 때 범위를 벗어나지 않도록 함
        {
            if (s[left] != s[right]) { // 양쪽 문자가 같지 않으면 더 이상 팰린드롬이 아님
                break;
            }
            cnt += 2; 		 // 팰린드롬 길이 증가
            left--; right++; // 양쪽으로 한 칸씩 확장
        }
        answer = max(answer, cnt);

        cnt = 0; // 짝수 길이 팰린드롬 탐색을 위해 카운트 초기화
        int l = i - 1, r = i; // 중심이 되는 위치를 현재 문자와 이전 문자 사이로 설정
        while (0 <= l && r < n) // 마찬가지로 양쪽으로 탐색
        {
            if (s[l] != s[r]) { // 양쪽 문자가 같지 않으면 중단
                break;
            }
            cnt += 2; // 팰린드롬 길이 증가
            l--; r++; // 양쪽으로 확장
        }
        answer = max(answer, cnt); 
    }

    return answer; 
}

 

---

 

 

다른 풀이

 

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

int solution(string s){ // 주어진 문자열 s에서 가장 긴 동일 문자로 이루어진 부분 문자열의 최대 길이를 반환하는 함수
    int n = s.size(); 
    int answer = 1; // 최소 하나의 문자로 이루어진 부분 문자열이 존재하므로 기본값을 1로 설정
    
    for (int i = 0; i < n; i++) // 문자열의 각 문자에 대해 반복
    {
        int cnt = 1; // 현재 문자를 포함하여 동일 문자로 이루어진 부분 문자열의 길이 카운트
        int left = i-1, right = i+1; // 현재 문자의 양 옆 인덱스

        while (0 <= left && s[left] == s[i]){ // 현재 문자와 같은 왼쪽 문자들을 탐색
            left--; // 왼쪽으로 이동
            cnt++;  // 카운트 증가
        }
        while (right < n && s[right] == s[i]) { // 현재 문자와 같은 오른쪽 문자들을 탐색
            right++; // 오른쪽으로 이동
            cnt++; 	 // 카운트 증가
        }

        // 현재 문자를 중심으로 왼쪽과 오른쪽에 동일한 문자가 없는 경우
        while (0 <= left && right < n && s[left] == s[right]) { // 양쪽으로 확장하여 동일 문자를 탐색
            left--;   // 왼쪽으로 이동
            right++;  // 오른쪽으로 이동
            cnt += 2; // 양쪽에서 하나씩 추가되므로 카운트 2 증가
        }

        answer = max(answer, cnt);
    }

    return answer;
}