코딩테스트 -- 가장 긴 팰린드롬 - (프로그래머스 / C++)

프로그래머스

 

문제!

---

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

 

---

요약하면 abccba 처럼 뒤집어도 똑같은 문자열이 되는 부분의 최대 길이를 구하는 문제!

 

 

여기서 놓칠수 있는 부분이 팰린드롬 문자열을 만들수 있는 방법에는 2가지가 있다는것!

1. abccba 완전 뒤집

2. abcZcba 한 문자 기준으로 뒤집

 

이렇게 두가지가 있는데 2번만 보고있다가 좀 헤멨네요;;

 

문자열의 길이가 2500 밖에 안되기에 그냥 탐색 해주면 될것 같습니다!

 

 

바로시작!

 

먼저 answer의 최솟값은 1개짜리 문자열! 1로 선언해주고  탐색에 필요한 인덱스 변수를 선언

    int answer=1;
    int index=0;
    
    int in1=0;
    int in2=0;
    
    for(int i=1;i<s.length()-1;i++){// 기준점

 

 

먼저

 

 

1번 조건 abccba 

투포인터 방식으로 두 인덱스를 따로 이동하여 같은지 탐색 해주었습니다!

in1=i;
in2=i+1;

while(true){//양쪽이 대칭 ABCCBA
            if(in2==s.length() or in1==-1){//끝도달
                break;
            }
            if(s[in2]!=s[in1]){//다름
                break;
            }
            in1-=1;
            in2+=1;
        }
        answer=max(answer,(in2-i-1)*2);

 

 

 

다음은 2번 조건! abcZcba 

 

index라는 한 변수를 증가시켜주며 현재 지점으로부터 양쪽으로 이동시키며 탐색!

        index=1;
        while(true){
            if(i+index==s.length() or i-index==-1){//끝도달
                break;
            }
            if(s[i-index]!=s[i+index]){//다름
                break;
            }
            index+=1;
        }
        answer=max(answer,(index-1)*2+1);

 

여기까지가 끝이네요 level 3문제치곤 쉬운문제였습니다!

 

 

ALL

#include <iostream>
#include <string>

#include <algorithm>
using namespace std;


int solution(string s){
    int answer=1;
    int index=0;
    
    int in1=0;
    int in2=0;

    for(int i=1;i<s.length()-1;i++){//기준점
        
        index=1;

        in1=i;
        in2=i+1;
        
        while(true){//양쪽이 대칭 ABCCBA
            if(in2==s.length() or in1==-1){//끝도달
                break;
            }
            if(s[in2]!=s[in1]){//다름
                break;
            }
            in1-=1;
            in2+=1;
        }
        answer=max(answer,(in2-i-1)*2); 
        
        while(true){//한숫자를 기준으로 양쪽이 같을때
            if(i+index==s.length() or i-index==-1){//끝도달
                break;
            }
            if(s[i-index]!=s[i+index]){//다름
                break;
            }
            index+=1;
        }
        answer=max(answer,(index-1)*2+1); 

    }
    
    return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!