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

hansol_Shin·2021년 4월 14일

알고리즘 프로그래머스

Algorithm

목록 보기

2/12

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

문제설명

문자열 s가 주어졌을 때 가장 긴 팰린드롬 sub-string의 길이를 return 하는 문제이다.

접근 방법 1

처음에는 2중 for 문을 사용하여 sub-string과 reverse-sub-string의 문자열을 비교하는 방법으로 접근하였다.
제한 조건이 s의 최대 길이가 2500이므로 O(n^2)은 문제가 없다 생각했는데 reverse 함수가 O(n)인걸 간과했다...

풀이 1

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int solution(string s)
{
    int answer=0;
    for(int j=0;j<s.length();j++){
        string tmp;
        for(int i=j;i<s.length();i++){
            string p;
            tmp += s[i];
            p=tmp;
            reverse(p.begin(),p.end());	// p를 거꾸로 하여
            if(tmp == p && answer < tmp.length()){	// tmp와 비교
                answer = tmp.length();	// answer 보다 크면 바꿔주기
            }
         }
    }
    return answer;
}

결과 1

접근 방법 2

sub-string이니까 for문 한번 꼭 써야하고, sub-string의 각 문자를 비교하니까 for문을 한번 더 써야하는데... reverse()를 안쓰는게 중요한 것 같다.
reverse()가 전체 비교를 할려 하는건데, 바꿨을 때 순서가 같다는게 앞뒤가 똑같으면 된다는거잖아요? 그래서 뭔가 연산을 줄일 생각이 스쳤다.
가장 앞, 가장 뒤 2개 문자 비교하면서 같으면 가장 앞을 오른쪽 한칸 가장 뒤를 왼쪽 한칸 옮기기 를 반복한다.
bool형 변수를 두고 다르면 false 처리를 한 뒤 다음 문자열로 넘어간다.
가장 긴 문자를 return 하는것이니 가장 긴 문자부터 시작해서 비교하고, 만약 팰린드롬이면 그 문자길이가 최대!!! ~~이거 생각하는데 애먹음 난 왜케 멍청하지~~

풀이 2

#include <iostream>
#include <string>
using namespace std;
int solution(string s)
{
    int answer=0;
    for(int i = s.length();i>0;i--){	// sub-string의 길이 i
            for(int j=0;j<=s.length()-i;j++){
                int l = j;
                int r = i-1+j;
                bool pal = true;
                while(l<r){
                    if(s[l]!=s[r]){
                        pal = false;
                        break;
                    }
                    l++;r--;	// 다음 문자 인덱스로 넘기기
                }
                if(pal){	// 팰린드롬이 맞으면 return
                    return answer = i;
                }
            } 
    }
    return answer;
}