Algorithm/LeetCode
[EASY] longest-palindrome
JunGi Jeong
2023. 1. 11. 11:00
문제 유형은 Hash Table, String, Greedy 문제이다.
주어진 문자열로 만들 수 있는 가장 긴 회문의 길이를 반환하는 문제이다.
/*
문제 파악 및 재정의
palindrome이란 회문 앞으로 뒤로 해도 같은 문장을 의미함
주어진 문자열 s로 만들 수 있는 가장 긴 회문의 길이를 반환하시오.
자료구조 및 알고리즘 설계
회문을 만들려면 무엇을 해야 할까
어떤 알파벳이 복수개 이상 존재한다면 해당 알파벳으로 앞 뒤를 설정하여 회문을 완성 할 수 있다.
그 외 단수개의 알파벳의 경우 가운데 넣어서 추가함으로써 회문의 길이를 늘릴 수 있음
Wednesday
e?e 3
apple
p?p 3
구현
중복되는 알파벳을 지울때마다 2씩 추가
남은 문자열의 길이가 0이 아니라면 +1 0이면 그대로 반환
*/
class Solution {
public int longestPalindrome(String s) {
int result = 0;
int degree = 0;
boolean check = true;
int length = s.length();
char compareChar = 'a';
if(length == 1) return 1;
for(int idx = 65; idx < 91; idx++){
compareChar = (char)idx;
s = s.replaceAll(compareChar+"", "");
int temp = s.length();
if((length - temp) % 2 == 1 && check){
result += 1;
check = !check;
}
result += ((length - temp) / 2) * 2;
length = temp;
}
for(int idx = 97; idx < 123; idx++){
compareChar = (char)idx;
s = s.replaceAll(compareChar+"", "");
int temp = s.length();
if((length - temp) % 2 == 1 && check){
result += 1;
check = !check;
}
result += ((length - temp) / 2) * 2;
length = temp;
}
return result;
}
}
회고
for문을 두 개 썼는데 좀더 줄일 수 있을듯 하고 약 40분정도 소요됐는데 더 빠르게 해결할 수 있도록 하자.