[Leetcode/Hash Map+Sorting] 3167. Better Compression of String

 

---

알고리즘:

• 주어진 문자열을 파싱하여 문자 -> 빈도 형태로 해시맵에 저장
• 해시맵의 키(문자)를 알파벳 순으로 정렬
• 최종 결과 문자열을 생성

from collections import defaultdict

class Solution:
    def betterCompression(self, compressed: str) -> str:
        freq_map = defaultdict(int)
        i = 0
        n = len(compressed)
        
        # 문자열을 순회하면서 문자와 숫자 파싱
        while i < n:
            char = compressed[i]
            i += 1
            num_start = i
            
            # 숫자 부분을 찾음
            while i < n and compressed[i].isdigit():
                i += 1
            freq = int(compressed[num_start:i])
            
            # 빈도수를 누적 저장
            freq_map[char] += freq
        
        # 알파벳 순으로 정렬 후 결과 문자열 생성
        result = "".join(f"{char}{freq_map[char]}" for char in sorted(freq_map))
        
        return result

 

🔹 시간 복잡도:

• 문자열을 한 번 순회하면서 파싱 (O(N))
• 해시맵을 정렬 (O(K log K), K는 문자 종류의 개수, 최대 26)
• 결과 생성 (O(K))
• 총합: O(N + K log K) → 사실상 O(N) 에 가까운 성능
  (알파벳 개수가 고정이므로 K는 26 이하)

🔹 공간 복잡도: O(K) (해시맵에 26개 이하의 키 저장)

 

---

📌 defaultdict란?

defaultdict는 Python의 collections 모듈에 있는 딕셔너리(dictionary) 서브클래스이다.
기본 dict와 비슷하지만, 존재하지 않는 키에 접근할 때 자동으로 기본값을 설정해주는 기능이 있다.

 

• defaultdict(int): 키가 없을 때 자동으로 0이 기본값으로 설정됨.
• defaultdict(list): 키가 없을 때 자동으로 [] (빈 리스트)가 기본값으로 설정됨.
• defaultdict(str): 키가 없을 때 자동으로 "" (빈 문자열)가 기본값으로 설정됨.
• defaultdict(set): 키가 없을 때 자동으로 set() (빈 집합)이 기본값으로 설정됨.

🔹 isdigit() 함수란?

Python의 문자열 메서드인 isdigit()은 문자열이 숫자로만 이루어져 있는지 확인하는 함수이다.
문자열의 모든 문자가 숫자(0~9)로만 이루어져 있으면 True를 반환하고,
그 외의 문자가 포함되어 있으면 False를 반환한다.

isdigit()의 특징

1. 정수 형태(0-9)만 인식
   • 소수점(.), 음수 기호(-), 공백 등은 숫자로 인정되지 않음.
2. 유니코드 숫자도 인식 가능
   • 아라비아 숫자뿐만 아니라 유니코드 숫자도 True를 반환.

s = "12345"
print(s.isdigit())  # True (숫자로만 이루어짐)

s = "12a45"
print(s.isdigit())  # False ('a'가 포함됨)

s = "3.14"
print(s.isdigit())  # False (소수점 '.'이 포함됨)

s = " 123"
print(s.isdigit())  # False (공백이 포함됨)

 

https://leetcode.com/problems/better-compression-of-string/