내 기준 생각이 좀 많이 필요한 문제였다.
처음에 했던 섣부른 생각.
오름차순 정렬을 한 뒤, 배열의 맨 첫 요소와 맨 마지막 요소의 차를 구해서 D보다 크면 배열의 마지막 원소를 하나씩 처내는 것이었다.
그렇게 작성한 코드다.
네개의 테스트 케이스에서는 성공했지만, 제출을 누르니 5/10이 떴다.
지금 생각해보면 왜 이런 생각을 했나 싶다.
아래와 같은 반례가 있기 때문이다.
난 단순히 배열의 맨 마지막 요소부터 순차적으로 처내면 된다고 생각했는데,
맨 첫 요소가 삭제되어야 하는 경우도 존재했다.
많은 고민 끝에 '투포인터'가 떠올랐다.
먼저 배열의 첫요소부터 길이 1의 구간을 잡고, 구간의 길이가 D를 초과하지 않는다면 to를 더해서 구간을 오른쪽으로 한 칸 씩 늘린다.
그 상태에서 구간의 길이가 D를 초과하는지 다시 검사하고, 초과한다면 구간의 앞부분을 하나씩 처내는 것이다.
오른쪽으로 꿈틀꿈틀 기어가는 애벌레를 생각하면 된다.
더 큰 구간의 길이가 나타나면, max값을 업데이트 해준다.
최종적인 max값을 N에서 빼주면 된다.
코드는 아래와 같다.
while문이 핵심.
👍👍
...