[백준 #16472] 고냥이 - Python

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

16472번: 고냥이

---

---

먼저 생각할 수 있는 방법은 완전탐색이다.

 

모든 글자를 시작점으로 하여 다음 글자들을 한 글자씩 포함시키고, 인식할 수 있는 알파벳의 종류를 초과할 때까지 포함을 진행한다. 인식할 수 있는 알파벳의 종류를 초과한 순간에 저장된 문자열의 길이가 인식할 수 있는 문자열의 길이이므로, 이 길이들의 최댓값을 구하면 간단하게 답을 구할 수 있다.

 

위 내용을 코드로 구현하면 아래와 같다.

#시간초과
n = int(input())
str = input()

max_str_length = 0
lower = 0
upper = 0

for i in range(len(str)):
    alpha = []
    str_length = 0
    for j in range(i,len(str)):
        if str[j] not in alpha:
            if len(alpha) < n:
                alpha.append(str[j])
                str_length +=1
            else:
                if max_str_length < str_length:
                    max_str_length = str_length
                break
        else:
            str_length += 1

print(max_str_length)

다만, 위 코드를 백준에 제출하였을 때, 시간초과가 발생한다. 위 코드는 for 반복문을 이중으로 돌기 때문에 시간복잡도가 O(n²)으로 크다.

 

그렇다면 시간복잡도를 줄일 수 있는 방법은?

투포인터를 활용하면 된다.

 

투포인터에 대한 기본 개념이 궁금하다면, 아래 링크의 다른 문제 해설에 있는 설명을 참고하도록 하자.

https://youngandmini.tistory.com/5

---

번역의 대상이 될 문자열을 두 포인터 사이의 문자열이라고 하자.

두 포인터를 모두 문자열의 시작점에 둔다.

이후 조건에 위배되지 않는 한, 오른쪽 포인터를 증가시킨다.

 

만약 조건에 위배되는 곳이 생겼다면?

조건에 맞았던 현재까지의 길이를 저장하고(최댓값인지 체크하여 업데이트), 다시 조건에 위배되지 않을 때까지 왼쪽 포인터를 증가시킨다. 이해를 돕기 위해 예를 들어 설명하면 다음과 같다.

 

[이해를 위한 예시]

"aaaaabbbb"라는 문자열이 있고, N=1이라고 하자.
왼쪽 포인터를 [ , 오른쪽 포인터를 ] 라고 하자.

[ ] aaaaabbbb 부터  [ aaaaa ] bbbb 까지는 오른쪽 포인터가 증가한다.
이후 [ aaaaab ] bbb 가 되는 순간, [ aaaaa ] 문자열의 길이 5를 최댓값으로 업데이트하고, 이제는 왼쪽 포인터를 증가시킨다.
aaaaa [ b ] bbb 가 되면 더 이상 조건에 위배되지 않는다. 이제부터 다시 오른쪽 포인터를 증가시킨다.
aaaaa [ bbbb ] 가 되면 오른쪽 포인터가 끝에 도달했으므로 종료가 되고, 현재 길이 4가 저장된 최댓값인 5보다 작으므로 답은 5가 된다.

---

투포인터 알고리즘을 사용하면, 오른쪽 포인터를 문자열 끝까지 이동시키는 횟수와 왼쪽 포인터를 문자열 끝까지 이동시키는 횟수를 합쳐서 (2 × 문자열의 길이) 정도의 while 문을 반복하게 되기 때문에 결과적으로 O(n)의 시간복잡도를 가지게 된다!

 

위 아이디어를 코드로 구현하면 아래와 같다.

n = int(input())
str = input()
str_len = len(str)

max_length = 0
lower = 0
upper = 0

map = dict()

length = 0
while lower <= upper < str_len:
    if str[upper] in map:
        map[str[upper]] += 1
        length+=1
        upper +=1
        continue
    else:
        if len(map) < n:
            map[str[upper]] = 1
            length += 1
            upper+=1
            continue
        else:
            if map[str[lower]] == 1:
                if length > max_length:
                    # print(map)
                    # print(str[lower:upper])
                    max_length = length
                map.pop(str[lower])
                lower+=1
                length-=1
                continue
            else:
                if length > max_length:
                    # print(map)
                    # print(str[lower:upper])
                    max_length = length
                map[str[lower]] -= 1
                lower += 1
                length -= 1
                continue

if max_length < upper - lower:
    # print(map)
    # print(str[lower:upper])
    max_length = upper - lower

print(max_length)