20922. 겹치는 건 싫어

문제

백준 20922번 겹치는 건 싫어

---

풀이

최장 연속 부분 수열을 구하는 전형적인 투포인터 문제다.
난이도가 실버 1이었던 거에 비해 쉬운편이었던 것 같다.

주어진 정수들에 대해 개수를 세야하기 때문에 딕셔너리를 활용했다.
딕셔너리는 참 편해서 조타🤗

부분수열의 왼쪽 끝, 오른쪽 끝을 표시하는 l, r을 통해 최장 길이를 구한다.

l, r은 각각 0부터 시작하는데,

• 만약 부분수열에서 a[r]의 개수가 이미 k개라면
  • longest 갱신
  • 가장 왼쪽 원소 지우고, 개수 1 감소 -> l += 1, cnt[a[l]] -= 1
• a[r]의 개수가 k개 미만이면
  • a[r]의 개수 1 증가
  • 다음 원소로 이동 -> r += 1

그리고 고려해야할 것이 r이 마지막원소를 가리킬 때 즉, n-1이 됐을 때는 현재 부분수열에서 a[r]의 개수에 따라 longest 값을 갱신해준 뒤 루프를 종료한다.

n, k = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
cnt = {x:0 for x in a}
longest = 0

l, r = 0, 0
while True:
    if r == n-1:
        longest = max(longest, r-l+1) if cnt[a[r]] < k else max(longest, r-l)
        break
    if cnt[a[r]] == k:
        longest = max(longest, r-l)
        cnt[a[l]] -= 1
        l += 1
    else:
        cnt[a[r]] += 1
        r += 1
print(longest)

---

부족한 점

언제나 투포인터 문제를 풀때면 인덱스에러를 마주한다.

문제유형에 따라 포인터의 종료지점 및 종료조건을 잘 파악해서 제발 while의 브레이크가 안고장나도록 하자