백준 16472 고냥이 Python3

https://www.acmicpc.net/problem/16472

16472번: 고냥이

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ16472.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

N = int(input())
text = input()
if len(text) == 1:
    print(1)
elif len(set(text)) <= N:
    print(len(text))
else:
    left = 0
    right = 1
    sets = set([text[left]])
    ans = 0
    while left < len(text)-1:
        if right == len(text):
            ans = max(ans, right-left)
            break
        sets.add(text[right])
        if len(sets) == N:
            ans = max(ans, right-left+1)
            right += 1
        elif len(sets) > N:
            sets.clear()
            left += 1
            sets.add(text[left])
            right = left + 1
        else:
            right += 1
    print(ans)

---

풀이 과정

풀이 시간 35분

N = int(input())
text = input()

#문자열 길이가 1인 경우, 번역기가 인식할 수 있는 최대 문자열의 길이는 1이다
if len(text) == 1:
    print(1)
    
#문자의 종류가 N보다 적게 구성된 문자열이라면, 문자열의 길이가 번역기가 인식할 수 있는 최대 문자열 길이다
elif len(set(text)) <= N:
    print(len(text))
    
else:
    left = 0
    right = 1
    sets = set([text[left]])
    ans = 0
    
    while left < len(text)-1:
    	#마지막 문자까지 번역이 가능한 경우, 정답 갱신 후 while문을 종료한다(다음을 탐색할 필요가 없다)
        if right == len(text):
            ans = max(ans, right-left)
            break
        
        #right 포인터에 있는 문자를 계속 sets에 추가해나가며 문자 종류의 개수를 체크한다
        sets.add(text[right])
        
        #문자 종류가 N개가 된 경우, 정답 갱신 후 다음 문자를 탐색하기 위해 right 포인터 값을 1 늘린다
        if len(sets) == N:
            ans = max(ans, right-left+1)
            right += 1
        #문자 종류가 N개를 초과한 경우, sets를 초기화하고 left 포인터 값과 right 포인터 값을 조정한다
        elif len(sets) > N:
            sets.clear()
            left += 1
            sets.add(text[left])
            right = left + 1
        #문자 종류가 N개 미만인 경우, 다음 문자 탐색을 위해 right 포인터 값을 1 늘린다
        else:
            right += 1
    print(ans)
#시간복잡도 = O(n), 공간복잡도 = O(n)