[백준 20922 🥈] 겹치는 건 싫어

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

20922번: 겹치는 건 싫어

문제풀이

• 투 포인터를 이용할 것을 떠올리지 못해서 풀이를 참고했다 ㅠㅠ
• https://khu98.tistory.com/187

[백준OJ] 20922번 겹치는 건 싫어

각 원소들의 개수가 저장된 count 배열을 이용했다.

처음에 start, end = 0,0으로 초기 위치를 셋팅해주고, end 포인터가 가리키는 배열 원소의 개수가 K개 미만이라면 해당 수의 count 배열값을 +1해주고, end 포인터를 한 칸 전진해준다. 

end 포인터를 전진해줄 수 있는 만큼 전진하다가, 어떤 원소의 개수가 k개 이상이 되어 더 이상 전진할 수 없어지면, start 포인터를 움직이기 시작한다.

위와 같이 end 포인터가 움직일 수 없는 경우, start 포인터를 한 칸 전진해주고, start 포인터가 가리키는 배열 원소의 개수를 -1 해주고, start 포인터를 한 칸 전진해준다.

그리고 각각의 요소에 대해 count 배열을 확인하고 start 포인터를 움직이거나 end 포인터를 움직일 때마다 가장 긴 수열의 길이를 저장한 ans 변수를 end-start와 비교해서 더 큰 값으로 갱신해준다. 

end 포인터가 모든 원소를 탐색할 때까지 반복한다.