[백준][파이썬] 20922번 겹치는건싫어

 2161번 : 카드1

문제

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

100,000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다. 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

입력

첫째 줄에 정수 N (1≤N≤200,000)과 K(1≤K≤100)가 주어진다.

출력

조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.

링크

20922번: 겹치는 건 싫어 (acmicpc.net)

20922번: 겹치는 건 싫어

 

 접근 방법

1. n, k, 수열 a를 입력 받고
2. 중복 원소의 개수를 세기 위해 cnt 리스트 생성
   1. cnt 리스트의 원소는 0으로 초기화
   2. cnt 리스트의 길이는 a 리스트의 최댓값 + 1
3. 수열 내에서 최장 수열을 찾아야 하므로 찾으려는 수열의 시작과 끝을 가리킬 left와 right라는 투 포인터를 0으로 초기화
4. right 포인터가 가리키는 a 리스트의 원소의 개수(cnt[a[right]])를 계속해서 체크
   
   1. 만약 k 보다 작다면 → cnt[a[right]] 값 1 증가, right 값 1 증가
   2. 만약 k 보다 크거나 같으면 → cnt[a[elft]] 값 1 감소, left 값 1 증가
5. right-left (현재 투 포인터가 가리키는 배열의 길이) 값과 이전 ans와 비교하여 최장 길이를 ans로 지정
   1. 반복문 안에서 가능한 모든 수열의 길이가 ans 값이 될텐데 그 중 최장 길이를 선택하도록 max 함수 사용

+ 투포인터 참고 자료 : [알고리즘] 투 포인터(Two Pointers) — y-seo의 딩코 기록들 (tistory.com)

[알고리즘] 투 포인터(Two Pointers)

 

 전체코드

import sys

n, k = map(int,sys.stdin.readline().split())
a = list(map(int,input().split()))

left, right, ans = 0, 0, 0
cnt = [0] * (max(a) + 1)

while right < n:
    if cnt[a[right]] < k:
        cnt[a[right]] += 1
        right += 1
    else:
        cnt[a[left]] -= 1
        left += 1
    ans = max(ans, right-left)

print(ans)