409. Longest Palindrome

https://leetcode.com/problems/longest-palindrome/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

 

/**
    1. 문제 해석하기
    가장 긴 palindrome 만들기
    2. 문제 풀이 방향
    홀수는 한개(가장 긴 홀수를 찾아야함)
    짝수는 전부
    하면 무조건 palindrome을 만들 수 있을 것 같음.
 */
class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int result = 0;
        boolean flag = false;
        int max = 0;

        for(int i = 0; i < s.length(); i++) {
            char temp = s.charAt(i);
            map.put(temp, map.getOrDefault(temp, 0) + 1);
        }

        for(Character c: map.keySet()) {
            if (map.get(c) % 2 == 0) {
                result += map.get(c);
                System.out.println(c + ", " + map.get(c));
            } else {
                flag = true;
                if (map.get(c) > 1) {
                    result += map.get(c) - 1;
                }
            }
        }
        if (flag) 
            result += 1;

        return result;
    }
}

 

Map이 아니라 a~Z까지만 나오는 거라서 int나 char로도 풀 수 있다는 것을 1등의 풀이를 통해서 알게되었다..

좀 변경해보겠다.

 

동일한 로직이었는데 int[]로 푸니 아래와 같이 시간이 단축되었다.

 

2ms

/**
    1. 문제 해석하기
    가장 긴 palindrome 만들기
    2. 문제 풀이 방향
    홀수는 한개(가장 긴 홀수를 찾아야함)
    짝수는 전부
    하면 무조건 palindrome을 만들 수 있을 것 같음.
 */
class Solution {
    public int longestPalindrome(String s) {
        int[] count = new int[128];
        int result = 0;
        
        for(int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'A']++;
        }
        boolean flag = false;
        for(int c: count) {
            if (c == 0) {
                continue;
            }

            if (c % 2 == 0) {
                result += c;
            } else {
                result += c - 1;
                flag = true;
            }
        }
        if (flag) {
            result += 1;
        }
        return result;
    }
}