Daily LeetCode Challenge - 2131. Longest Palindrome by Concatenating Two Letter Words

Problem From.

https://leetcode.com/problems/longest-palindrome-by-concatenating-two-letter-words/

오늘 문제는 주어진 배열에서 단어들을 이어붙여서 가장 긴 palindrome (앞으로 읽어도 거꾸로 읽어도 같은 단어) 를 만드는 문제였다.

처음에는 이중 for 문을 사용하여 모든 원소들을 하나씩 비교하려고 하였지만 그렇게 하면 실행시간이 너무 길어지고 복잡해지기 때문에 HashMap 을 사용하였다.

리스트를 처음부터 검사하면서, 중복되는 값이 없으면 map 에 넣고, 중복되는 값이 있으면 map 에서 빼면서 answer 를 4씩 증가시켜 주었다.

그리고 gg 와 같이 혼자서도 palindrome 을 이루는 단어는 가운데에 딱 한개 들어가면서 answer 의 길이를 2 늘려줄 수 있으므로, 마지막에 map 을 한번 검사하면서 넣을 수 있으면 넣어주었다.

이때 검사하는 조건은 그 key 값이 혼자서도 palindrome 이면서 answer 을 2로 나눈 값이 짝수여야 했다.

abcddcba 와 같이 8자리인 palindrome 은 2로 나누어도 그 길이의 반이 짝수 이지만,
abcdggdcba 와 같이 이미 가운데에 palindrome 인 단어가 들어가면 10인 길이를 반으로 나누면 홀수가 남기때문이다.

class Solution {
    fun longestPalindrome(words: Array<String>): Int {
        
        var answer = 0
        
        val map = HashMap<String, Int>()
        
        var hasMiddle = false
        
        words.forEach { word ->
            
            if(word.reversed() == word) hasMiddle = true
            if(map.containsKey(word.reversed())) {
                if(map.get(word.reversed())!! > 1) {
                    map.put(word.reversed(), map.get(word.reversed())!! - 1)
                }else {
                    map.remove(word.reversed())
                }
                answer += 4
            }else {
                map.put(word , map.getOrDefault(word , 0) + 1)
            }
            
        }
        
        map.forEach { entry ->
            if(hasMiddle && (answer / 2) % 2 == 0 && (entry.key.reversed() == entry.key)) answer += 2
        }
        
        
        return answer
    }
}

위와 같은 방식으로 O(N) 의 Time Complexity 를 얻을 수 있었다.