[백준 16472] 고냥이 (Python)

www.acmicpc.net/problem/16472

16472번: 고냥이

 

문제풀이

N, S : 입력값

check : 알파벳 개수

left, right : 투 포인터

tmp : 인식한 문자 개수

q : 현재 인식한 문자열

 

투 포인터(Two-Pointer) 를 이용하여 새로 인식한 글자와 문자열의 길이를 계산해 문자열의 최대 길이를 구할 수 있다.

 

1. 투 포인터를 이용해 왼쪽부터 오른쪽 방향으로 하나씩 글자를 인식한다.

- 인식한 문자 개수(tmp) 가 N 인데, 새로운 글자가 나타나면 ans 갱신

- 새로 인식한 문자 개수 증가

 

2. 왼쪽 인덱스를 증가시키면서 시작 문자를 변경한다.

- q(현재 인식한 문자열) 에 있는 가장 좌측 문자를 제거하고 해당 문자 개수 감소

- q에 가장 좌측 문자의 개수가 0이면 인식한 문자 개수(tmp) 감소

 

3. 1, 2 과정을 반복한다.

 

4. 결과(ans) 출력

 

코드

import sys
from collections import deque

if __name__ == '__main__':
    N = int(input())
    S = list(map(str, sys.stdin.readline().rstrip()))
    check = [0] * 26 # 알파벳 개수 세기
    size = len(S)
    left, right = 0, 0 # 투 포인터
    ans, tmp = 0, 0 # tmp : 인식한 문자 개수
    q = deque() # 현재 인식한 문자열

    while left < size and right < size:
        while right < size:
            if tmp == N and not check[ord(S[right]) - ord('a')]: # 인식한 글자 개수가 N인데 새로운 글자가 나타나면 break
                break
            if not check[ord(S[right]) - ord('a')]: # 인식한 글자 개수가 N개 이하일 때 새로운 글자 나타나면
                tmp += 1 # 인식한 문자 개수 증가
            check[ord(S[right]) - ord('a')] += 1 # 알파벳 개수 증가
            q.append(S[right])
            right += 1 # right 증가

        ans = max(ans, len(q))
        # 첫 문자 없애주기
        first = q[0]
        check[ord(first) - ord('a')] -= 1 # 첫 문자 알파벳 개수 감소
        q.popleft()
        if not check[ord(first) - ord('a')]: # 첫 문자 알파벳 개수가 0이면
            tmp -= 1 # 인식한 문자 개수 감소
        left += 1 # left 증가
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!