You are given a string s and an integer repeatLimit. Construct a new string repeatLimitedString using the characters of s such that no letter appears more than repeatLimit times in a row. You do not have to use all characters from s.
Return the lexicographically largest repeatLimitedString possible.
A string a is lexicographically larger than a string b if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the longer string is the lexicographically larger one.
Example 1:
Input: s = "cczazcc", repeatLimit = 3
Output: "zzcccac"
Explanation: We use all of the characters from s to construct the repeatLimitedString "zzcccac".
The letter 'a' appears at most 1 time in a row.
The letter 'c' appears at most 3 times in a row.
The letter 'z' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "zzcccac".
Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.
Example 2:
Input: s = "aababab", repeatLimit = 2
Output: "bbabaa"
Explanation: We use only some of the characters from s to construct the repeatLimitedString "bbabaa".
The letter 'a' appears at most 2 times in a row.
The letter 'b' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "bbabaa".
Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.
Constraints:
- 1 <= repeatLimit <= s.length <= 105
- s consists of lowercase English letters.
일단 문제 설명부터 솔직히 잘 이해가 안 된다.
아 뭐이리 복잡헌지 원-_-
그치만, 뭐 대충 읽다보면 그래도 슬 이해가 가는 기적적인 Description.
확실히 잘은 모르지만 Python의 Counter 함수를 import해서 쓰면 잘 풀릴 거 같은 느낌이 든다.
이 기회에 일단 내 능력껏 풀어보고, Counter 함수를 잘 써보는 걸로
1. Python
아 수많은 for문을 세팅해서 test case를 뚫어 냈건만. .또 Time limit에 벽에 부딛혔다 ㅠㅠ
class Solution:
def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
# Make a counting MAP of string s
dic = {}
for x in s :
if x not in dic :
dic[x] = 1
else : dic[x] += 1
# Reverse sorting
temp = sorted(s,reverse=True)
# Iteratively make new string considering a Rule provided
curr = temp[0]
cnt = 1
for i in range(1,len(temp)):
# 연속으로 같은 친구를 만났다.
if temp[i] == curr:
cnt += 1
# 아직 reapeat limit에 걸리지 않았다.
if cnt <= repeatLimit:
continue
# repeat limit에 걸려버렸다.
else :
cond_break = True
for j in range(i+1,len(temp)):
if temp[j]!=curr:
curr = temp[j]
temp[i],temp[j] = temp[j],temp[i]
cnt = 1
cond_break = False
break
# Could not find next biggest charcter
if cond_break:
temp = temp[:i]
break
# 다른 친구를 만났다.
else :
curr = temp[i]
cnt = 1
return "".join(temp)
모범 답안은 아래와 같다.
검토좀 해봐야지..
from collections import Counter
class Solution:
def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
# 1. 문자 빈도수 계산 및 정렬
freq = Counter(s)
sorted_chars = sorted(freq.keys(), reverse=True) # 사전순 내림차순 정렬
result = []
i = 0 # 현재 처리 중인 문자 인덱스
while i < len(sorted_chars):
char = sorted_chars[i]
count = freq[char]
# 현재 문자를 repeatLimit 만큼 사용
use_count = min(count, repeatLimit)
result.extend([char] * use_count)
freq[char] -= use_count
if freq[char] == 0:
# 현재 문자를 모두 사용했으므로 다음 문자로 이동
i += 1
else:
# repeatLimit 때문에 더 이상 사용할 수 없는 경우
# 다음 가능한 문자를 찾아 하나만 삽입
next_char_found = False
for j in range(i + 1, len(sorted_chars)):
next_char = sorted_chars[j]
if freq[next_char] > 0:
result.append(next_char)
freq[next_char] -= 1
next_char_found = True
break
# 다음 가능한 문자가 없으면 종료
if not next_char_found:
break
return "".join(result)# TWO POINTER 사용
class Solution:
def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
chars = sorted(s, reverse=True)
result = []
freq = 1
pointer = 0
for i in range(len(chars)):
if result and result[-1] == chars[i]:
if freq < repeatLimit:
result.append(chars[i])
freq += 1
else:
pointer = max(pointer, i + 1)
while pointer < len(chars) and chars[pointer] == chars[i]:
pointer += 1
if pointer < len(chars):
result.append(chars[pointer])
chars[i], chars[pointer] = chars[pointer], chars[i]
freq = 1
else:
break
else:
result.append(chars[i])
freq = 1
return ''.join(result)
2. C++
C++로는 heap과 map을 사용한다.
#include <unordered_map>
#include <queue>
class Solution {
public:
string repeatLimitedString(string s, int repeatLimit) {
unordered_map<char,int> freq;
for(char const c:s){
freq[c]++;
}
priority_queue<pair<char,int>> pq;
for(auto& [c, count] : freq){
pq.push({c,count});
}
string result;
while(!pq.empty()){
auto [ch, count] = pq.top();
pq.pop();
int useCount = min(count,repeatLimit);
result.append(useCount, ch);
count -= useCount;
if(count > 0){
if(pq.empty()) break;
auto [next_ch, next_count] = pq.top();
pq.pop();
result.push_back(next_ch);
next_count-=1;
if(next_count > 0) pq.push({next_ch,next_count});
pq.push({ch,count});
}
}
return result;
}
};
3. C
char* repeatLimitedString(char* s, int repeatLimit) {
int freq[26] = {0}; // 알파벳 빈도수 배열
int len = strlen(s);
// 1. 문자 빈도수 계산
for (int i = 0; i < len; i++) {
freq[s[i] - 'a']++;
}
// 2. 결과 문자열을 저장할 동적 메모리 할당
char* result = (char*)malloc(sizeof(char) * (len + 1));
int index = 0; // 결과 문자열의 인덱스
int lastChar = -1; // 마지막으로 사용한 문자
int lastCharCount = 0; // 마지막 문자의 연속 사용 횟수
while (1) {
int added = 0; // 문자를 추가했는지 여부
// 3. 큰 문자부터 순회 (z -> a)
for (int i = 25; i >= 0; i--) {
if (freq[i] == 0) continue; // 빈도수가 0이면 건너뜀
// 같은 문자를 연속해서 너무 많이 사용했을 때
if (lastChar == i && lastCharCount >= repeatLimit) {
continue; // 다른 문자를 찾아야 함
}
// 사용할 수 있는 문자 결정
result[index++] = 'a' + i; // 결과 문자열에 추가
freq[i]--; // 빈도수 감소
added = 1;
// 마지막 문자 및 연속 사용 횟수 업데이트
if (lastChar == i) {
lastCharCount++;
} else {
lastChar = i;
lastCharCount = 1;
}
break; // 문자 하나를 추가했으면 반복문 종료
}
// 문자를 추가하지 못한 경우 종료
if (!added) break;
}
// 결과 문자열 종료
result[index] = '\0';
return result;
}