[PCCP] 문자열과 해시함수 [5]

▼ Why ?

이번 문제도 이전 문제들처럼 문자열에서 문자들의 빈도수를 체크해 해결하는 문제이고, 문자의 빈도수를 다루는 문제들에 익숙해지기 위해 풀어보았다.

---

▼ 팰린드롬 (Palindrome)

 

문제 정보

• 문자열이 주어지면 해당 문자열의 문자들을 가지고 만들 수 있는 최대길이 팰린드롬을 만들고 그 길이를 구하세요.
• 문자열은 소문자로만 이루어져 있습니다.
• 만약 "abcbbbccaaeee" 가 주어진다면 만들 수 있는 가장 긴 팰린드롬은 "ebbcaaacbbe"이고 답은 11입니다.

 

입출력 예

 

제한사항

• s의 길이는 1,000을 넘지 않습니다.

 

어떻게 해결해야 할까?

1. 문자들의 빈도수를 다루는 문제이기 때문에, 일단 key(문자)-value(빈도수)를 쌍으로 하는 HashMap class의 instance(' chFreq ')를 생성하여 값을 저장한다
2. 그다음 int형 변수 ' oddCnt ' 를 하나 생성해 빈도수가 홀수인 문자들의 개수를 저장한다
3. 그리고 입력받았던 문자열의 길이에서 ' oddCnt ' 의 값을 빼주고, 가운데에 위치한 문자의 개수는 홀수여도 팰린드롬이 될 수 있기 때문에 1까지 더해준다
4. 그 값이 입력받은 문자열의 문자들로 만들 수 있는 가장 긴 팰린드롬의 길이라고 할 수 있다

 

해결 코드

import java.util.*;

class Solution {
    public int solution(String str) {
        HashMap<Character, Integer> chFreq = new HashMap<>();
        
        for(char ch : str.toCharArray()) {
            chFreq.put(ch, chFreq.getOrDefault(chFreq, 0) + 1);
        }
        
        int oddCnt = 0;
        
        for(char key : chFreq.keySet()) {
            if(chFreq.get(key) % 2 != 0) oddCnt++;
        }
        
        return oddCnt == 0 ? str.length() : str.length() - oddCnt + 1;
    }
}

 

---

▼ 정리

 

• 문자의 빈도수 관련 문제는 문자열로부터 읽어온 문자나 숫자를 key 값으로 하고 빈도수를 value 값으로 하는 HashMap의 instance를 생성하고, 그 instance를 기반으로 해결해나가는 것이 핵심인 것 같다
  ( ' getOrDefault() ' 메서드 덕분에 값을 저장하는 코드도 간결하게 작성할 수 있다 )
  
  
• 삼항 연산자를 이용해서 코드를 좀 더 간결하게 작성해보았다