알고리즘(C++) / 프로그래머스 level 3 : 가장 긴 팰린드롬

level 3 : 가장 긴 팰린드롬

https://programmers.co.kr/learn/courses/30/lessons/12904?language=cpp 

코딩테스트 연습 - 가장 긴 팰린드롬

 

코드

//프로그래머스 가장 긴 팰린드롬
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int palindrome(string& s, int left, int right) {
    while (left >= 0 && right < s.size()) { //이동할 수 없을때까지
        if (s[left] != s[right])
            break;
        left--; //왼쪽으로 이동
        right++; //오른쪽으로 이동
    }
    return right - left - 1; // 거리
}


int solution(string s) {
    int answer = 1;
    
    for (int i = 1; i < s.size(); i++) {
        int left = i - 1; 
        int right = i + 1;
        int odd = palindrome(s, left, right);
        int even = palindrome(s, left, right - 1);
        answer = max({ answer, odd, even }); //최대값 구하기
    }
    return answer;
}

int main() {
    string s = "ABCCBA";
    cout << solution(s) << "\n";
    return 0;
}

 

설명

• 한 지점에서 left와 right의 위치를 구한다. 
• 한 지점을 기준으로 홀수 길이와 짝수 길이를 구할 수 있다. 
• palindrome함수에서 left 위치의 문자와 right 위치의 문자가 같지 않을 때까지 구하고 만족하여 팰린드롬의 길이를 return 한다. 
• answer은 odd, even, answer의 최대값을 구한다.

 

고찰

걸린시간 : 1시간이상 이후 구글링

문제는 간단하게 풀었지만 효율성 테스트에서 1번 통과를 못해서 결국 구글링으로 풀었다.

전에 코드를 어떻게 푼지 기억이 안나서 효율성이 얼마나 차이나는지 비교는 못하겠지만 그렇게.. 많이 차이 났던거 같지 않은데...ㅠㅠㅠ

효율성 문제가 존재하면 반복문을 최대한 많이 안쓰도록 구현을 해야한다.