Construct String With Repeat Limit

첫 번째 시도

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        ret = ''
        d = {}
        used = []

        for s in s:
            if s in d:
                d[s] += 1
            else:
                d[s] = 1
                used.append(s)
        
        used.sort(reverse=True)

        for i in range(len(used)):
            if d[used[i]] > repeatLimit:
                d[used[i]] -= repeatLimit
                ret += "".join([used[i]]*repeatLimit)

                if i + 2 > len(used):
                    break

                while d[used[i]] != 0:
                    tmp = i + 1
                    while d[used[tmp]] == 0 and tmp < len(used):
                        tmp += 1
                        if tmp + 1 > len(used):
                            break
                    if tmp + 1 > len(used):
                        break

                    ret += used[tmp]
                    d[used[tmp]] -= 1
                    
                    if d[used[i]] > repeatLimit:
                        ret += "".join([used[i]]*repeatLimit)
                        d[used[i]] -= repeatLimit
                    else:
                        ret += "".join(used[i] * d[used[i]])
                        d[used[i]] = 0
            else:
                ret += "".join([used[i]]*d[used[i]])
                d[used[i]] = 0
        return ret

어찌저찌 풀어냈는데, 40분 정도 걸린 것 같다. 문제를 이해하는 데 10분, 코드 작성하는 데 20분, 예외처리하는 데 10분 정도인 것 같다. 머릿속에서는 처리하는 논리 구조가 그려지는 데, 이걸 코드로 표현하는 게 어려운 것 같다.

GPT’s 리팩토링

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        from collections import Counter

        # Step 1: Count the frequency of each character and sort them in descending order
        char_count = Counter(s)
        sorted_chars = sorted(char_count.keys(), reverse=True)

        result = []
        while sorted_chars:
            # Step 2: Take the largest available character
            current_char = sorted_chars[0]
            current_count = min(char_count[current_char], repeatLimit)
            
            # Add the character up to the repeatLimit times
            result.append(current_char * current_count)
            char_count[current_char] -= current_count

            if char_count[current_char] == 0:
                sorted_chars.pop(0)

            # Step 3: If there are still characters left for current_char but cannot repeat further
            if char_count[current_char] > 0:
                # Find the next largest character to break the sequence
                if len(sorted_chars) > 1:
                    next_char = sorted_chars[1]
                    result.append(next_char)
                    char_count[next_char] -= 1

                    if char_count[next_char] == 0:
                        sorted_chars.pop(1)
                else:
                    # No other characters available to break the sequence, so we stop
                    break

        return "".join(result)

내장함수를 이용해서 코드 길이가 더 짧아졌다. 그리고 일단 추가할 수 있는 만큼 문자를 추가한 뒤에 if 로직을 둔 것도 더 나아 보인다.

Step 3에서 나는 tmp 변수를 이용해서 out of index error 를 핸들링하기 위해 2개의 break 문을 사용해야 했다. 반면 gpt의 경우 pop을 이용해 남은 문자 종류의 개수를 확인하는 식으로 해결했다.

결국 내 코드는 loop가 중첩되었고, gpt는 하나의 루프로 해결했다. runtime도 40ms 정도 차이가 났다.

마무리

• python 내장 함수를 이용하자.
• 솔직히 혼자 풀어낸 걸로 만족한다. 대견한 나.