•
문제 설명 : 제공된 문자열 중 연속된 3자리 문자열을 잘랐을 때, 중복되지 않은 알파벳으로 사용된 문자열을 몇 개 만들 수 있는지 반환
•
풀이 방법
◦
간단하게 index 접근으로 조건에 맞는 문자열이 몇개인지 확인하였다.
•
시간복잡도 :
•
성공 코드
class Solution:
def countGoodSubstrings(self, s: str) -> int:
result = 0
if len(s) < 3:
return 0
# 조건에 만족하는 문자열이 있는지 확인
# O(N)
for i in range(len(s) - 2):
if s[i] != s[i + 1] and s[i + 1] != s[i + 2] and s[i] != s[i + 2]:
result += 1
return result
Python
복사
•
해시테이블을 사용한 코드(ChatGPT)
해시 테이블을 사용한 풀이는 하지 못해서, 해시 테이블을 사용한 방법을 찾았지만 시간 복잡도의 큰 차이는 없고 오히려 가독성이 더 좋지 않아 참고만 하면 좋을 듯 하다.
class Solution:
def countGoodSubstrings(self, s: str) -> int:
result = 0
if len(s) < 3:
return 0
# 슬라이딩 윈도우 초기화
window = defaultdict(int)
# 초기 윈도우 설정
for i in range(2):
window[s[i]] += 1
for i in range(2, len(s)):
window[s[i]] += 1
if len(window) == 3:
result += 1
# 윈도우의 첫 번째 요소 제거
window[s[i - 2]] -= 1
if window[s[i - 2]] == 0:
del window[s[i - 2]]
return result
JavaScript
복사