본문으로 건너뛰기

2131 - Longest Palindrome by Concatenating Two Letter Words

info

풀이 키워드​

스포주의

해시


풀이 코드​

info
  • 메모리: 57700 KB
  • 시간: 103 ms
class Solution {
    public int longestPalindrome(String[] words) {
        Map<String, Integer> diffHash = new HashMap<>();
        Map<String, Integer> sameHash = new HashMap<>();
        int ans = 0;

        for (String w : words) {
            if (w.charAt(0) == w.charAt(1)) {
                sameHash.merge(w, 1, Integer::sum);
            }
            else {
                String rw = new StringBuilder(w).reverse().toString();
                int v = diffHash.getOrDefault(rw, 0);
                if (v == 0) {
                    diffHash.merge(w, 1, Integer::sum);
                }
                else {
                    ans += 4;
                    diffHash.merge(rw, -1, Integer::sum);
                }
            }
        }

        boolean hasMid = false;
        for (int v : sameHash.values()) {
            if (0 < v) {
                ans += v >> 1 << 2;
                if ((v & 1) == 1) hasMid = true;
            }
        }

        return ans + (hasMid ? 2 : 0);
    }
}

풀이 해설​

al, la 와 같이 서로 다른 문자로 구성된 문자열의 처리는 diffHash로,
aa 와 같이 같은 문자 구성의 문자열은 sameHash로 분리하여 처리했다.

그리고 diffHash의 경우 하단과 같은 추가 분기 로직이 들어간다.


나는야 솔로​

String rw = new StringBuilder(w).reverse().toString();
int v = diffHash.getOrDefault(rw, 0);
if (v == 0) {
    diffHash.merge(w, 1, Integer::sum);
}

원본 문자열을 w, 뒤집은 문자열을 rw라고 하자.

diffHash에서 rw를 검색하여 w의 팰린드롬 짝이 있는지 판별한다.

없으면 얌전히 w로 해싱한다.


나는야 커플​

else {
    ans += 4;
    diffHash.merge(rw, -1, Integer::sum);
}

반대로, 짝이 있다면 팰린드롬 형성이 가능하므로

최종 문자열 길이는 w와 rw 길이의 합인 4만큼 늘어난다.

그리고 짝을 지어줬기 때문에 rw값을 1 빼도록 한다.


완벽한 친구들​

sameHash에 들어가는 녀석들은 같은 문자끼리 구성되었기 때문에 혼자서도 팰린드롬이다.

하지만 동일한 친구가 하나 더 있다면 짝으로도 처리 가능하기 때문에 다음과 같이 로직을 구성한다.

boolean hasMid = false;
for (int v : sameHash.values()) {
    if (0 < v) {
        ans += v >> 1 << 2;
        if ((v & 1) == 1) hasMid = true;
    }
}

return ans + (hasMid ? 2 : 0);

hasMid는 최종 문자열의 정 가운데에 완벽한 녀석을 넣을 것인지의 여부를 뜻한다.

물론 짝을 지을 수 있으면 그게 더 이득이라, 짝이 없는 녀석이 있을때에만 (즉, 해시값이 홀수일때만) true로 설정한다.

짝이 있다면 최대한 다 짝지어서 그만큼 최종 문자열 길이에 합산해준다.


메모​

  • 그냥 무난하고 재미있는 난이도