프로그래머스. 가장 긴 팰린드롬 (구현)

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

프로그래머스

인덱스를 이용한 구현 문제이다. 나는 문제를 못풀어서 아래 링크를 참고했다. 

처음 풀 때도 정답과 비슷한 알고리즘으로 풀었던 거 같은데, 꼬인 것같다. 이전 코드를 저장을 안해둬서 어디서 실수했는지 모르겠다. 

이 문제 풀때 시간 복잡도와 관련해서도 고민을 했었어서, 정답 코드로 시간 복잡도도 계산해봤다. 

 

1. 특징

1) 인덱스 관련 구현

 

2. 삽질 포인트

1) 회전 과정에서 이미 값을 덮어버린 좌표값이 새로운 좌표값의 값으로 들어가게 설정하는 등의 실수들이 있어서 시간이 오래걸렸다. 

대입할 좌표는 그대로 두고, 가져올 좌표값을 i나 j로 변경한다.

(ex. board[curx][j] = board[curx][j-1];)

2. 구현 포인트

*빈칸을 사이에 두고 대칭인 경우(ex. abba)와 특정 문자를 두고 대칭인 경우(ex.aba)를 구분해야한다

1) for문을 돌면서 s를 순회한다. 현재 char 인덱스를 기준으로 좌우를 비교하여 팰린드롬이면 left, right 인덱스를 양 끝단으로 보낸다. (aba 경우)

2) 현재 char 인덱스를 기준으로 좌,현재 값을 비굑하여 팰린드롬이면 left, right 인덱스를 양 끝단으로 보낸다. (abba 경우)

 

 

3. 코드

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

int palin(string s, int left, int right) // 블로그 참고 코드
{
    int ssize = s.size();
    while(left >= 0 && right < ssize)
    {
        if(s[left] != s[right])
        {
            break;
        }
        
        left -= 1;
        right += 1;
    }
    return right - left - 1;
}

int palin1(string s, int left, int right) // 내가 짠 코드
{
    int ssize = s.length();
    if(s[left] != s[right])
    {
        return 1;
    }
    while(left-1 >= 0 && right+1 < ssize)
    {
        left -= 1;
        right += 1;
        
        if(s[left] != s[right])
        {
            left+=1;
            right-=1;
            break;
        }
        
        
    }
    
    return right - left + 1;
}

int solution(string s)
{
    int answer = 1;
    int ssize = s.size();
    int odd, even;
    for(int i = 1; i < ssize; i++)
    {
        int left = i-1;
        int right = i+1;
        odd = palin(s, left, right);
        even = palin(s, left, right-1); 
        answer = max({answer, even, odd});    
    }
    return answer;
}

 

빈칸을 사이에 두고 대칭인 경우(ex. abba)와 특정 문자를 두고 대칭인 경우(ex.aba)를 구분해서