[백준] 16472번 고냥이 (투포인터 문제)

사용 언어 - Python3

문제 -  16472번 고냥이

 

투포인터 : 가능성을 지워주는 방법

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

16472번: 고냥이

 

정답

(투포인터) 양쪽 끝에서 비교하면서 만나면 종료

알파벳 종류가 n넘지 않는지 확인 + 최대 개수 확인

 

arr.rstrip() 불필요한 공백 제거

s = 시작포인터 = 0

e = 끝포인터 = 0

letters = [] 알파벳 종류 넣을 리스트

letters.append(arr[s]) 첫번째 값을 일단 넣고 시작

dist = 0 인식할 수 있는 최대 개수

 

s와 n이 len(arr)를 넘지 않는 구간일 때 반복문 진행

1. len(letters) <= n 인식할 수 있는 알파벳 개수라면,

한개 더 인식 e += 1

arr[e] 가 letters에 있지 않다면 = 겹치는 문자가 아니라면, letters.append(arr[e])

 

2. len(letters) > n 인식할 수 없는 알파벳 개수라면, 리셋 + 초기화

s = s+1

e = s

letters = [arr[s]]

해당 s+1 위치부터 새롭게 시작

 

dist = max(dist,e-s+1) = 인식할 수 있는 문자열의 최대 개수 = max로 더 큰 값 있으면 계속 update

print(dist)

import sys
input = sys.stdin.readline

n = int(input()) # 번역기가 인식할 수 있는 알파벳 최대 개수
arr = list(input().rstrip()) # 문자열 알파벳 소문자

s = 0
e = 0
letters = []
letters.append(arr[s]) # 맨 앞 1개 인식하고 시작
dist = 0

while s < len(arr) and e < len(arr):
    dist = max(dist,e-s+1)
    if len(letters) <= n: # 인식할 수 있는 알파벳 개수라면
        e += 1 # 한 개 더 인식
        if e < len(arr) and arr[e] not in letters:
            letters.append(arr[e]) # 해당 알파벳 추가

    if len(letters) > n: # 인식할 수 없다면 리셋! 새롭게 시작
        s = s+1
        e = s
        letters = [arr[s]]
print(dist)

 

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/16472_%EA%B3%A0%EB%83%A5%EC%9D%B4.py