🎯문제
앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.
예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.
제한사항
- 문자열 s의 길이 : 2,500 이하의 자연수
- 문자열 s는 알파벳 소문자로만 구성
입출력 예
| s | answer |
|---|---|
| "abcdcba" | 7 |
| "abacde" | 3 |
입출력 예 설명
입출력 예 #1
4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.
입출력 예 #2
2번째자리 'b'를 기준으로 "aba"가 팰린드롬이 되므로 3을 return합니다.
✏️풀이
코드
class Solution {
// 팰린드롬인지 확인하는 메소드
public boolean isPalindrome(String s, int start, int end) {
// 처음부터 진행하고 끝에서부터 진행하는 수가 교차하는 순간 종료
while(start <= end) {
// 처음부터 진행하는 값과 끝에서부터 진행하는 값이 다를 경우
if(s.charAt(start++) != s.charAt(end--)) {
// false를 반환
return false;
}
}
return true;
}
public int solution(String s) {
// s의 길이만큼 반복
for(int i = s.length(); i > 0; i--) {
// i + j의 값이 s의 길이보다 클 경우 반복 종료
for(int j = 0; j+i <= s.length(); j++) {
// 팰린드롬인지 확인
if(isPalindrome(s, j, i + j - 1)) {
return i;
}
}
}
return 0;
}
}설명
직접 구현을 하여 해결하였다.
팰린드롬이란 앞뒤를 뒤집어도 똑같은 문자열을 뜻하는데, 이를 확인하기 위해서는 시작점과 끝점부터 하나씩 증가하고 감소시켜가면서 값을 비교하면 된다. 이렇게 순차적으로 확인을 하다가 시작점과 끝점이 만나거나 교차되는 순간 반복문을 종료하면 된다. 반복문이 종료되기 전에 값이 다른 것이 확인됐을 경우 팰린드롬이 되지 않기 때문에 false를 반환하고 반복문이 종료될 때까지 다른 것이 확인되지 않았을 경우 true를 반환한다.
solution 메소드에서는 s의 길이만큼 반복을 진행한다. 이때 i는 끝에서부터 감소해나가는 값이며, j는 시작점을 뜻한다. 끝지점을 고정시켜놓고 시작점을 움직여가면서 탐색을 진행한다. 이때 팰린드롬인지 확인하여 통과한다면 그때 i의 값을 반환해준다. 이때 i의 값을 반환시켜주는 이유는 가장 끝지점부터 탐색을 진행하기 때문에 자연스럽게 먼저 팰린드롬인지 확인이 된다면 그 값이 제일 긴 팰린드롬이 되며, 해당 길이는 i를 통해서 알 수 있기 때문이다.
따라서 반복문을 진행하면서 팰린드롬인지 확인이 된다면 i의 값을 반복문을 모두 빠져나올 때까지 반환되는 값이 없다면 0을 반환해준다면 문제를 해결할 수 있다!
💡느낀 점
단순 구현을 사용한 문제였는데, 팰린드롬을 확인하기 위해서 reverse() 를 사용하다가 효율성 부분에서 계속 막혔다. 따라서 해당 부분을 직접 구현을 해주었는데, 안될 줄 알았으나 바로 해결이 되어서 기쁘면서도 화가 났다. 원래 reverse라는 함수롤 몰랐다면 직접 구현을 했을 문제였는데, 함수를 알고 있던 게 오히려 독이 되었다. 문제를 풀 때 효율성 관련한 부분에서는 생각을 안하고 있었는데, 함수를 무조건 쓴다고 좋은 것은 아니구나를 다시 한 번 뼈저리게 느낄 수 있었다..
링크
