[99클럽 코테 스터디] 38일차 TIL 그리디

 

 

오늘의 문제는 LeetCode

 

409. Longest Palindrome

 

 

문제

 

 

 

문제 설명 

대문자 또는 소문자로 구성된 문자열 s가 주어졌을 때 회문으로 만들수 있는 총 글자수를 반환하는 문제입니다. 

[입력 예시]

s = "abccccdd"

[출력 예시]

7

 

 

 

 

문제 풀이 시간 

권장 풀이 시간은 60분이었고, 저는 42분이 걸렸습니다.

 

 

 

문제 접근 방식

먼저 해시맵을 생성해 문자열 s의 각 문자와 해당 문자의 빈도수를 저장합니다. 그 다음 저장된 각 문자의 빈도수를 확인하며 짝수인 경우에는 최종 길이에 더합니다. 빈도수가 홀수인 경우에는 해당 빈도수에서 1을 뺀 값을 길이에 더하고 isOdd를 true로 설정합니다. 

빈도수가 홀수인 문자가 있다면 최종 길이에 1을 더해 반환합니다. 

 

 

 

문제 풀이

import java.util.*;

class Solution {
    public int longestPalindrome(String s) {
        
        Map<Character, Integer> map = new HashMap<>();
        int len = 0;
        boolean isOdd = false; 

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

        for(int cnt : map.values()) {
            if(cnt % 2 == 0) {
                len += cnt;
            } else {
                isOdd = true;
                len += cnt - 1; 
            }
        }

        if(isOdd) {
            len += 1;
        }

    return len;     
    }

}

 

 

첫 번째 시도

첫 번째 시도에서 입력 값이 s ="abccccdd" 일 때 정답은 7이지만 반환값은 11이었습니다. 

루프 내에서 빈도수를 가져와서 짝수일 때 len에 더하고 홀수일 때 len에 빈도수 - 1을 더하는 방식을 사용했는데 여기서 문제가 발생한 것입니다. 

해시맵에 값을 추가하면서 동시에 홀수와 짝수일 때의 길이를 계산하려고 했더니 같은 문자가 여러번 등장할 때마다 길이를 누적 계산하게 되어 값이 중복적으로 더해지는 문제가 있었습니다. 

import java.util.*;

class Solution {
    public int longestPalindrome(String s) {
        
        Map<Character, Integer> map = new HashMap<>();
        int len = 0; 
        boolean isOdd = false; 

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

            if(map.get(s.charAt(i)) % 2 == 0) {
                len += map.get(s.charAt(i));
            } else {
                len += map.get(s.charAt(i)) - 1;
                isOdd = true; 
            }
        }

        if(isOdd) {
            len += 1;
        }


    return len;     
    }

}

 

 

 

 

빈도수가 짝수인 경우와 홀수인 경우

빈도수가 짝수인 경우

문자의 빈도수가 짝수이면, 회문을 만들 때 대칭적으로 만들 수 있기 때문에 해당 문자의 빈도수를 최종 길이에 그대로 더합니다. 

빈도수가 홀수인 경우 

회문은 대칭이어야 하기 때문에 홀수 빈도수의 문자는 최대 하나만 사용할 수 있습니다. 따라서 해당 빈도수에서 1을 뺀 값을 길이에 더하고, 홀수 빈도수가 존재하는지 판별하기 위한 isOdd 변수를 true로 설정합니다. 만약 빈도수가 홀수인 문자가 하나라도 존재하면 회문의 중앙에 하나의 문자를 배치할 수 있다는 것이므로 최종길이에 1을 더해 반환합니다. 

 

 

 

 

문자 출현 빈도수 구하기 

해시맵의 getOrDefault() 메서드를 사용해 빈도수를 구할 수 있습니다. getOrDefault()는 특정 문자가 맵에 존재하는지 확인하고 존재하면 해당 문자와 연결된 값을 반환하고, 존재하지 않으면 지정된 값을 반환하는 메서드입니다. 반환된 값에 1을 더해 해당 문자의 새로운 빈도수를 계산하고 put() 메서드를 사용해 이를 맵에 업데이트 하면 빈도수를 구할 수 있습니다. 

 

 

다른 풀이 알아보기 

아래 코드는 해쉬셋 대신 배열을 사용한 풀이입니다. 문자의 아스키코드 값을 인덱스로 사용해서 빈도수를 직접 저장하는 방식을 사용해 빈도수에 대한 접근을 빠르게 할 수 있습니다. 

문자열의 각 문자를 순회하면서 배열의 해당 인덱스를 업데이트 합니다. 짝수 빈도수를 가진 문자는 회문에 포함시키기 위해 길이 res에 2를 더하고 홀수 빈도수를 가진 문자는 하나만 회문에 사용할 수 있기 때문에 oddCnt를 사용해 홀수 빈도수의 개수를 확인합니다. 만약 홀수 빈도수가 하나 이상이라면 최종 길이에 1을 더합니다. 

이런 배열을 사용한 방식은 해시 테이블 보다 메모리 사용이 효율적이고 실행 속도도 빠릅니다. 

class Solution {
    public int longestPalindrome(String s) {
        
        if(s.length() == 1)return 1;
        
        // HashSet<Character> set = new HashSet<>();
        int[]set = new int[128];
        int res = 0;
        int oddCnt = 0;
        for(char ch : s.toCharArray()){
            if(set[ch]!=0){ // by default array all index value are 0 in java.
                res+=2;
                // set.remove(ch);
                set[ch] = 0;
                oddCnt--;
            }else{
                // set.add(ch);
                set[ch] = 1;
                oddCnt++;
            }
        }
        
//         if(set.size() > 0){
//             res+= 1;
//         }
        if(oddCnt > 0){res+= 1;}
        return res;
       
        /*HashMap<Character, Integer> map = new HashMap<>();
        int oddCnt = 0;
        int res = 0;
        for(char ch: s.toCharArray()){
            map.put(ch, map.getOrDefault(ch, 0)+1);
            int currFreq = map.get(ch);
            if(currFreq % 2 == 0){
                res+= 2;
                oddCnt--;
            }else{
                oddCnt++;
            }
        }
        if(oddCnt > 0){
            res+= 1;
        }
        return res;*/
        
        
    }
}

 

 

 

 

 

이렇게 오늘 38일차 TIL을 작성해 보았습니다.