https://www.acmicpc.net/problem/20922
시간 1초, 메모리 1024MB
input :
- N, K(1 <= N <= 200,000)(1 <= K <= 100)
- 모든 배열의 값들이 입력됨.(1 <= Ai <= 100,000)
output :
- 최장 연속 부분 수열의 길이를 출력
조건 :
- 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성하자.
일단 과거엔 물론, 과거에도 투 포인터를 알 고 있었는데 아직까지 확실하진 않았었다.
그래서 for문을 두번 써서 시간 초과를 내고 다른 한 경우는 그냥 start, end를 명시적으로만 만들고 for문을 돌린것과 동일하게 만들었다.
생각해보면 end를 기준으로 for문을 돌리고 어떤 숫자가 k 초과가 되었을 때 그때 while 문을 이용해서 start를 옮겨도 괜찮을 것 같다.
물론 while문을 이용해서 저렇게 짰다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
여기서 생각해 줘야 할 것은 각 숫자가 k개 초과해서 등장했는가인데. start 변수를 옮기려면 while말고는 생각나는 것이 없다.
그러고 end == n 일 경우에 예외처리가 필요하다.
import sys
n, k = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
num = [0] * 100001
start, end, length, ans = 0, 0, 0, 0
while start <= end:
if end == n:
if length <= ans:
break
else:
num[data[start]] -= 1
start += 1
length -= 1
if num[data[start]] <= k:
ans = max(ans, length)
continue
num[data[end]] += 1
length += 1
end += 1
if num[data[end - 1]] > k:
while num[data[end - 1]] > k:
num[data[start]] -= 1
start += 1
length -= 1
else:
ans = max(ans, length)
print(ans)
