[Lv3] 가장 긴 팰린드롬

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

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

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

제한사항

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

---

입출력 예

s	answer
abcdcba	7
abacde	3

 

입출력 예 설명

입출력 예 #1
4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

입출력 예 #2
2번째자리 'b'를 기준으로 aba가 팰린드롬이 되므로 3을 return합니다.

 

 

---

 

앞뒤가 똑같은 전화번호라든가 수박이박수라든가.. 로꾸거로꾸거로꾸거 말해말...

 

문자열은 알파벳 소문자로만 주어집니다.

 

스택을 두고 앞에서부터 쌓다가 해체한다? vsdffffffffffffffffdsv면 언제 해체할지 감 잡기도 힘들테고..

 

전 팰린드롬의 중간부터 찾을 겁니다. 어차피 중간의 거울위치인 대칭점에서는 확연한 특징이 있을테니까요.

 

 

팰린드롬은 2가지 형태일겁니다. ????ava???? 처럼 중간점이 하나인 것,

 

나머지는 ????avva???? 나 ????avvva???? 처럼 중간점이 두 개 이상인 것.

 

 

정규표현식으로 '특정문자'[a-z]'특정문자' 로 중간에 다른 문자가 들어간 것과

 

'특정문자'{2,}로 특정문자가 2개이상 반복되는 부분을 찾을 겁니다.

 

'특정문자'[특정문자]'특정문자'로 특정문자가 3개로 반복되어 중복되는 경우가 있더라도 상관없습니다.

 

public int solution(String s) {
    if(s.length()==0) return 0;
    char[] origin = s.toCharArray();
    String regex_base1 = "[a-z]";
    String regex_base2 = "{2,}";
    int max = 1;
    for(char c='a';c<='z';c++) {
        String regex1 = new StringBuilder().append(c).append(regex_base1).append(c).toString();
        String regex2 = new StringBuilder().append(c).append(regex_base2).toString();
        Matcher m1 = Pattern.compile(regex1).matcher(s);
        Matcher m2 = Pattern.compile(regex2).matcher(s);
        while(m2.find()) {
            int first = m2.start();
            int next = m2.end();
            int len = next-first;
            next--;
            while(true) {
                if(first==0||next==origin.length-1) break;
                else {
                    first--;
                    next++;
                    if(origin[first]==origin[next]) len+=2;
                    else break;
                }
            }
            if(len>max) max=len;
        }
        int fornext = 0;
        while(m1.find()) {
            int first = m1.start()+fornext;
            int next = m1.end()+fornext;
            fornext = first+1;
            int len = next-first;
            next--;
            while(true) {
                if(first==0||next==origin.length-1) break;
                else {
                    first--;
                    next++;
                    if(origin[first]==origin[next]) len+=2;
                    else break;
                }
            }
            if(len>max) max=len;
            String newstr = s.substring(fornext);
            m1 = Pattern.compile(regex1).matcher(newstr);
        }
    }
    return max;
}

주어진 문자가 아예없으면 당연히 0일테고,

 

초기 max값은 1로 시작합니다. 한글자만 덜렁 주어지면 그 자체로 1글자인 팰린드롬이 되니까요.

 

a부터 z까지 특정문자를 반복할겁니다.

특정문자가 a라면, 정규표현식은

a[a-z]a와 a{2,0} 두개를 생성합니다.

 

두번째 정규표현식부터 볼겁니다. 더 간단해서. 이 부분만 따로 떼와봅니다.

while(m2.find()) {
    int first = m2.start();
    int next = m2.end();
    int len = next-first;
    next--;
    while(true) {
        if(first==0||next==origin.length-1) break;
        else {
            first--;
            next++;
            if(origin[first]==origin[next]) len+=2;
            else break;
        }
    }
    if(len>max) max=len;
}

Matcher m2 = Pattern.compile(정규표현식).matchers(대상)에서,

m2.start()는 해당영역의 시작점을 평소처럼 가져오는데,

m2.end()는 해당영역의 종료점을 마지막 문자위치 이후(indexOf('종료위치문자')+1)로 가져와서,

길이계산에는 그대로 연산하지만, 이후에 위치정보로 쓰기 위해 -1해줍니다.

 

만약 first가 문자열의 처음이거나, next가 문자열의 끝이라면, 더 이상 비교할 구간이 없으므로 빠져나옵니다.

그게 아니라면, 각각 한칸씩 뒤로/앞으로 가면서 그 문자들 마저 같으면 길이가+2 됩니다. 다르면 빠져나오겠죠.

 

???aaaaaaaaaaa????????aaa???????aa?????????????aaaaaa?????라면 문제없이 각 4구간의 중심을 찾아 탐색합니다.

a가 아무리 많아도 {2,}로 주었기 때문에 정확히 양끝으로 잡아 원하는 구간씩 탐색합니다.

 

 

int fornext = 0;
while(m1.find()) {
    int first = m1.start()+fornext;
    int next = m1.end()+fornext;
    fornext = first+1;
    int len = next-first;
    next--;
    while(true) {
        if(first==0||next==origin.length-1) break;
        else {
            first--;
            next++;
            if(origin[first]==origin[next]) len+=2;
            else break;
        }
    }
    if(len>max) max=len;
    String newstr = s.substring(fornext);
    m1 = Pattern.compile(regex1).matcher(newstr);
}

a[a-z]a인 m1은 조금 더 과정이 많습니다.

 

fornext는 우선 신경쓰지 말기로합니다.

first와 next, len, 그리고 안의 while 과정은 m2과정과 같습니다.

 

헌데, Matcher의 find 동작은 다음과 같이 이루어집니다.

 

???ava???avava???aaaaa??? 일 때,

 

첫 ava 다음의 ava는 제대로 잡지만, ava를 통째로 들어내기 때문에 그 뒤의 ava는 인식하지 못합니다.

다음의 aaa도 마찬가지입니다. aaa를 통째로 들어내기 때문에 그 뒤의 aaa는 인식하지 못합니다.

(대신 앞서 했던 m2로 인해 aaaaa를 제대로 체크했겠죠.)

 

새로운 문자열에 대해 m1을 바꿀텐데,

ava를 들어내는게 아니라 앞의 a하나만 들어내면 중복된 검사도 피하고 다음 검색으로 충분히 이어집니다.

즉, 문자열을 초기 first값 다음칸부터 잘라내서 거기에 같은 Matcher를 실행하면 되는데,

first는 앞뒤로 늘리면서 변했기 때문에, 미리 fornext에 first+1를 뒀던겁니다.

String newstr = s.substring(fornext);

m1 = Pattern.compile(regex1).matcher(newstr);

 

어차피 문자열을 잘라써도 비교 자체는 맨 처음 만들었던 char[] 배열에서 이루어지므로 상관없습니다.

 

 

a-z까지 각각 m1,m2를 하고났을 때 최대길이를 반환하면 됩니다.