문자열 s와 숫자 k가 주어졌을 때, 문자열 s 안에서 두 번 이상 등장하는 길이 k의 부분 문자열이 몇 개인지 구하는 문제입니다.
문제 예시
예를 들어 입력이 다음과 같다고 가정해 보겠습니다.
- s = "xxxyyy", k = 2
이 경우 출력은 2가 됩니다. 길이가 2인 부분 문자열 중 "xx"와 "yy"가 각각 두 번 이상 나타나기 때문입니다.
풀이 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 모든 길이 k의 부분 문자열을 순서대로 추출하여 리스트에 저장합니다.
- 추출한 부분 문자열들의 등장 횟수를 카운트합니다.
- 등장 횟수가 1보다 큰(즉, 두 번 이상 나타나는) 부분 문자열의 개수를 합산하여 반환합니다.
구현 코드
아래 예제를 통해 더 자세히 이해해 보겠습니다.
class Solution:
def solve(self, s, k):
from collections import Counter
seen = []
for i in range(len(s) - k + 1):
t = s[i : i + k]
seen.append(t)
s = Counter(seen)
return sum(1 for x in s.values() if x > 1)
ob = Solution()
print(ob.solve("xxxyyy", 2))입력
"xxxyyy", 2
출력
2
코드 설명
range(len(s) - k + 1): 문자열에서 시작할 수 있는 모든 인덱스를 순회합니다. 길이 k의 부분 문자열은 총 len(s) - k + 1개 존재합니다.s[i : i + k]: 슬라이싱을 통해 현재 위치에서 길이 k만큼의 부분 문자열을 잘라냅니다.Counter(seen): collections 모듈의 Counter를 사용해 각 부분 문자열의 등장 횟수를 딕셔너리 형태로 집계합니다.sum(1 for x in s.values() if x > 1): 등장 횟수가 1보다 큰 경우만 세어 최종 결과를 반환합니다.
이 알고리즘의 시간 복잡도는 O(n × k)로, 여기서 n은 문자열의 길이, k는 부분 문자열의 길이입니다. Counter를 활용하면 반복 횟수 집계를 간결하고 효율적으로 처리할 수 있습니다.