서로 다른 구간 지우기

어떤 값 $x$가 수열에 $M$번 등장한다고 하자. 한 번의 연산에서 지우는 구간은 모든 원소가 서로 달라야 하므로, 한 번의 연산으로 값 $x$를 두 개 이상 지울 수 없다.

따라서 값 $x$를 하나 지우려면, 같은 연산에서 $x$가 아닌 원소도 적어도 하나 같이 지워져야 한다. 전체 원소 중 $x$가 아닌 원소는 $N-M$개뿐이므로, 값 $x$의 원소는 최대 $N-M$개만 지울 수 있다. 그러므로 최종적으로 적어도

$$M-(N-M)=2M-N$$

개의 $x$가 남아야 한다.

모든 값에 대해 생각하면, $M$을 가장 많이 등장하는 값의 등장 횟수라고 할 때 정답은 적어도

$$\max(0,2M-N)$$

이다.

이제 이 하한을 항상 달성할 수 있음을 보인다.

먼저 $M>N/2$라고 하자. 가장 많이 등장하는 값을 $x$라고 하자. 수열에 $x$가 아닌 원소가 남아 있다면, 현재 수열에는 $x$와 $x$가 아닌 원소가 인접한 위치가 반드시 존재한다. 그 두 원소는 서로 다르므로 길이 $2$ 구간으로 지울 수 있다. 이 연산을 반복하면 $x$가 아닌 모든 원소를 지울 수 있고, 그때마다 $x$도 하나씩 같이 지워진다. 따라서 최종적으로 $2M-N$개의 $x$만 남길 수 있다.

이제 $M \le N/2$인 경우를 보자. 이 경우에는 모든 원소를 지울 수 있다. 이를 현재 수열의 길이에 대한 귀납법으로 보일 수 있다.

현재 수열에서 가장 많이 등장하는 횟수를 $M$이라 하자.

• 길이가 $2$라면 두 원소는 서로 달라야 하므로 한 번에 지울 수 있다.
• 현재 길이를 $n$이라 하자. 어떤 최빈값의 등장 횟수가 충분히 작다면, 인접한 서로 다른 두 원소를 지워도 여전히 어떤 값도 절반을 초과하지 않는다. 따라서 귀납적으로 나머지를 모두 지울 수 있다.
• 절반에 가까운 최빈값이 있는 경우에도, 그 최빈값과 다른 값이 인접한 경계가 존재한다. 이 길이 $2$ 구간을 지우면 최빈값의 등장 횟수도 함께 줄어든다.
• 유일하게 주의할 경우는 길이가 홀수이고, 서로 다른 두 값이 각각 $(n-1)/2$번씩 등장하는 경우이다. 이때 나머지 한 원소가 두 종류 사이에 끼어 있으면 서로 다른 세 원소로 이루어진 길이 $3$ 구간을 지울 수 있고, 그렇지 않으면 두 최빈값이 인접한 길이 $2$ 구간을 지울 수 있다. 어느 경우든 지운 뒤에는 귀납 가정을 적용할 수 있다.

따라서 $M \le N/2$이면 모든 원소를 지울 수 있다.

결론적으로 정답은

$$\max(0,2M-N)$$

이다. 여기서 $M$은 수열에서 가장 많이 등장하는 값의 등장 횟수이다.

구현은 각 값의 등장 횟수를 세고 최댓값 $M$을 구하면 된다.

시간 복잡도는 $O(N)$이다.