문자열 s와 값 k가 주어져 있다고 가정해 보겠습니다. 여기서 k는 문자열 길이 n의 약수입니다. 이 경우 문자열 s를 크기가 k인 n/k개의 부분 문자열 t_i로 나눌 수 있습니다.
그런 다음 각 t_i를 이용하여 다음 조건을 만족하는 새로운 문자열 u_i를 만들어야 합니다.
u_i에 포함된 문자들은 반드시t_i에 존재하는 문자들이어야 합니다.중복된 문자는 제거되어,
u_i내에서 각 문자의 빈도는 정확히 1이 되어야 합니다.
즉, 우리가 찾아야 하는 것은 이러한 u_i 문자열들의 목록입니다.
문제 이해하기
예를 들어 입력이 s = "MMPQMMMRM", k = 3이라면 출력은 ["MP", "QM", "MR"]이 됩니다. 그 이유는 다음과 같습니다. 문자열 s의 길이는 9이고 k는 3이므로, 9/3 = 3개의 그룹으로 나뉩니다. 분할된 문자열은 "MMP", "QMM", "MRM"이지만, 중복 문자를 허용하지 않기 때문에 각각 "MP", "QM", "MR"로 변환됩니다.
해결 접근 방식
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- 인덱스 i := 0으로 초기화합니다.
- 결과를 저장할 리스트 ret을 생성합니다.
- 문자 등장 여부를 추적할 맵 mp를 생성합니다.
- 현재 그룹의 문자열을 담을 to_print를 빈 문자열로 초기화합니다.
- i가 문자열 s의 길이보다 작은 동안 다음을 반복합니다.
- i mod k가 0이면서 i가 0이 아니라면, 하나의 그룹이 완성된 것이므로 to_print를 ret에 추가하고 mp와 to_print를 초기화합니다.
- s[i]가 mp에 없다면, mp[s[i]] := 0으로 설정하고 to_print에 s[i]를 이어 붙입니다.
- i := i + 1로 증가시킵니다.
반복이 끝나면 마지막 남은 to_print를 ret에 추가한 뒤 ret을 반환합니다.
구현 예제
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
def solve(s, k):
i = 0
ret = []
mp, to_print = {}, ""
while i < len(s):
if i % k == 0 and i != 0:
ret.append(to_print)
mp, to_print = {}, ""
if s[i] not in mp.keys():
mp[s[i]] = 0
to_print += s[i]
i += 1
ret.append(to_print)
return ret
s = "MMPQMMMRM"
k = 3
print(solve(s, k))입력
"MMPQMMMRM", 3
출력
['MP', 'QM', 'MR']