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분 정도인 것 같다. 머릿속에서는 처리하는 논리 구조가 그려지는 데, 이걸 코드로 표현하는 게 어려운 것 같다.
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 정도 차이가 났다.