(Python3) - LeetCode (Medium) : 2182. Construct String With Repeat Limit

https://leetcode.com/problems/construct-string-with-repeat-limit

📕 풀이방법

📔 입력 및 초기화

key로는 알파뱃 value는 빈도 수를 저장할 해시맵 char_map, max_heap, 정답변수 answer, 이전 문자 prev를 선언 후 적절히 저장해줍니다. max_heap은 python에서 제공되지 않으므로 저장시 음수로 저장해줍니다.

📔 풀이과정

큰 문자부터 넣다가 reapeatLimit을 넘어가면 다음문자를 1개씩 넣어줍니다. 이 때 큰 문자와 이전에 넣은 문자가 같은 경우 적절히 빼서 repeatLimit만큼의 문자만 answer 뒤에 붙이도록 구현해야합니다.

 

max_heap에 원소가 있는 동안 다음을 진행합니다.

1. 이전에 있는 문자가 같고 남아있는 문자 빈도 수 + 1가 repeatLimit을 초과한다면 offset을 1로 만들어줍니다.

 

2. answer를 이전에 붙여준 문자를 고려해 repeatLimit을 넘지 않고 offset만큼 뺀 개수만큼 문자를 뒤에 붙여줍니다.

 

3. reapeatLimit만큼 붙여줬으므로 다음 문자를 pop해서 answer에 해당 문자를 1개 붙여줍니다.

 

4. 현재 문자와 다음 문자의 빈도수가 남아있다면 max_heap에 갱신된 빈도수와 함께 문자를 다시 넣어줍니다.

 

5. prev는 다음 문자로 갱신해줍니다.

📔 정답 출력 | 반환

answer를 반환합니다.

---

📕 Code

📔 Python3

from heapq import heappush, heappop
class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        char_map = {}
        max_heap = []
        for c in s:
            char_map[c] = char_map.get(c,0) + 1
        char_map = sorted(char_map.items(), key=lambda x:x[0],reverse=True)

        for char, freq in char_map:
            heappush(max_heap,(-ord(char), freq))

        answer, prev = '', ''

        while max_heap:
            minus_ord, freq = heappop(max_heap)

            char = chr(-minus_ord)
            offset = 0

            if char == prev and freq + 1 > repeatLimit:
                offset = 1
            answer += char * (min(freq,repeatLimit)-offset)

            if not max_heap:
                break

            minus_ord2, freq2 = heappop(max_heap)
            char2 = chr(-minus_ord2)
            answer += char2

            if freq > repeatLimit - offset:
                heappush(max_heap, (minus_ord, freq - (repeatLimit - offset)))
            if freq2 - 1 > 0:
                heappush(max_heap, (minus_ord2, freq2 - 1))

            prev = char2

        return answer

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.