[ 알고리즘 ] 코딩 - Programmers - 가장긴팰린드롬.java

---

문제 링크

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

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

---

문제 개요

프로그래머스 - Level 3 - (자바)가장 긴 팰린드롬 - 완전탐색, 투포인터 형식

문제

 

제한사항

 

입출력예시

앞뒤를 뒤집어도 똑같은 문자를 팰린드롬이라고 하고, 이 팰린드롬의 길이 중 가장 긴 것을 찾는 문제

이런 경우에도 팰린드롬이다

s = "a", s = "abcd"  -> 길이 1인 팰린드롬

s = "aa" s = "abcdee" -> 길이 2인 팰린드롬

---

 

로직

Step 01. 인덱스는 가장 왼쪽부터 시작해서 가장 끝까지 이동한다. ( i )

Step 02. left 인덱스는 i, right 인덱스는 문자열의 끝으로 준다

Step 03. left 인덱스의 문자와 right 인덱스의 문자를 비교. 같다면 left를 1 증가시키고, right를 1 감소 시킨다.

이때 팰린드롬의 길이를 +2 한다.

Step 03-1. 만약 문자가 다른 경우에는 left는 i값으로, right는 size -1 - idx 값으로 초기화 하고, idx를 1 증가시킨다

Step 04. Step 03의 과정을 left가 right보다 커질때까지 반복수행한다 ( while(left < right) )

Step 05. Step04의 과정이 끝난 후 left와 right가 같은 값을 가리키고 있다면 팰린드롬을 1 증가시켜준다

(이 팰린드롬은 홀수로 중간 지점이 존재한다)

Step 06. 최대치를 갱신한다.

Step 07. Step01의 반복이 다 끝나고 난 후의 최대치가 정답!

 

이해를 돕기위한 예시! s = "abacde"

** left와 right가 다른경우 left는 왼쪽에 고정하고 right만 이동

** left와 right가 같은 경우에는 left right 둘 다 이동!

 

** 인덱스 관리를 생각없이 했다가, 몇몇 테스트케이스를 통과하지 못했었다.

** 인덱스 관리에 조금 더 신경을 쓰자!

 

---

코드

class Solution {
	public int solution(String s) {
		int size = s.length();
		int max_length = Integer.MIN_VALUE; // 가장 긴 팰린드롬 저장

		for (int i = 0; i < size; i++) { // 가장 왼쪽부터 시작해서 가장 끝까지
			int left = i; // 한칸씩 이동
			int right = size - 1; // 오른쪽은 항상 끝이 시작
			int cur_length = 0; // 현재 팰린드롬 길이
			int idx = 1; // 몇번째 반복인지 알려줄 인덱스

			while (left < right) { // left가 right보다 작을때까지
				char left_c = s.charAt(left);
				char right_c = s.charAt(right);

				if (left_c == right_c) { // 같은 경우에는 둘 다 이동
					left++;
					right--;
					cur_length += 2; 
				} else { // 다른 경우에 다시 초기화
					cur_length = 0;
					left = i;
					right = size - 1 - idx;
					idx++;
				}
			}
			if (left == right) // 팰린드롬 중간에 문자가 있는 경우
				cur_length++;

			max_length = max_length > cur_length ? max_length : cur_length;

		}

		int answer = max_length;

		return answer;
	}
}