[Grind75-LeetCode] Longest Palindrome JAVA

반응형

728x90

[Grind75-LeetCode] Longest Palindrome - Easy 

---

접근

• 구현

---

풀이

주어진 문자열 s를 이용해 가장 긴 펠린드롬 문자의 길이를 구하는 문제이다. 소문자와 대문자 알파벳이 주어지고 각각 다른 문자로 취급하게 된다. 총 알파벳 52개를 사용해 가장 긴 펠린드롬의 길이를 구해야 한다. 

 

가장 긴 펠린드롬 문장을 모두 찾아라와 같은 문제였다면 귀찮았겠지만 길이를 구하는 문제이기 때문에 단순하게 구할 수 있다. 펠린드롬이란 앞으로 뒤로 읽어도 똑같은 문자를 말하는데 그러기 위해선 가운데를 기준으로 양쪽이 같아야 한다. 그 말은 알파벳의 수가 최소 2개 이상이어야 하고 모든 짝수개의 알파벳을 사용한 뒤 홀수개의 알파벳이 존재한다면 가운데로 끼워 가장 긴 길이를 구할 수 있다. 

     public int longestPalindrome(String s) {
        int[] abc = new int[52];

        for (char c : s.toCharArray()) {
            if (c >= 'a' && c <= 'z') {
                abc[c - 'a']++;
            } else if (c >= 'A' && c <= 'Z') {
                abc[c - 'A' + 26]++;
            }
        }

문제를 풀기 위해선 문자의 개수를 다 세어야 하는데 나는 거의 map을 사용하여 개수를 저장했는데 알파벳의 경우 아스키코드 값을 이용해 배열에 값을 저장할 수 있다. 배열을 사용하는 방법이 다른 방법보다 훨씬 성능이 좋아 이 방법을 사용하기로 했다. 0번 인덱스부터 25번까지는 소문자의 개수를 저장하고 26번부터 51번까지는 대문자의 개수를 저장한다.

	int result = 0;
        boolean isOdd = false;
        
        for (int a : abc) {
            if (a % 2 ==1) {
                result += a - 1;
                isOdd = true;
            }

            if (a % 2 == 0) {
                result += a;
            }
        }

        if (isOdd) {
            result++;
        }
        return result;
    }

결과를 저장할 변수를 선언하고 문자열 내 홀수개의 알파벳이 있는지 검사하는 변수를 하나 선언해줬다. 홀수개의 알파벳이 존재하는 경우 가운데 한 개의 알파벳을 추가해 길이를 늘일 수 있기 때문이다. 그리고 만들어진 배열을 순회하며 홀수 개 알파벳이 존재하는 경우 한 개를 뺀 짝수개를 사용하게 된다. 해당 알파벳이 3개라면 2개를 사용하여 문장을 늘릴 수 있기 때문이다. 짝수개인 경우는 해당 개수를 그대로 사용하게 되고 마지막으로 홀수개의 알파벳이 존재했다면 한 개를 추가해 최종 개수를 구하게 된다. 

---

전체 코드

class Solution {
    public int longestPalindrome(String s) {
        int[] abc = new int[52];

        for (char c : s.toCharArray()) {
            if (c >= 'a' && c <= 'z') {
                abc[c - 'a']++;
            } else if (c >= 'A' && c <= 'Z') {
                abc[c - 'A' + 26]++;
            }
        }

        int result = 0;
        boolean isOdd = false;
        
        for (int a : abc) {
            if (a % 2 ==1) {
                result += a - 1;
                isOdd = true;
            }

            if (a % 2 == 0) {
                result += a;
            }
        }

        if (isOdd) {
            result++;
        }
        return result;
    }
}