풀이 아이디어

n이 최대 200,000이므로
$O(n^2)$는 시간초과가 발생한다.
그래서 $O(n)$에 풀 수 있는 로직으로 작성해야했는데
0과 1의 조합해서

O의 개수: zero
1의 개수: one
이라고 한다면 각 조합별로 mex(S)의 결과값은

• (0,0) -> 1
• (0,1) -> 2
• (0,2+) -> 1

(0,0)쌍의 합은 (zero-1)zero/2
(0,1)쌍의 합은 zeroone
(0,2+)쌍의 합은 zero(n-zero-one)이다.

트러블슈팅

n=200,000이고
0이 100,000개, 1이 100,000개이면
문제에서 요구하는 값을 sum이라고 한다면
sum은 2100,000100,000=200억으로 넘어가 int의 범위를 벗어나는 값을 갖게된다.
sum을 long타입으로 선언해주고 더하는 값 역시 200억을 넘어갈 수 있으므로
(long)으로 변환해서 더해줘야했다.

sum += (long)(zero_count-1)*(zero_count)/2; // 0 전부 세기
sum += (long)zero_count*one_count*2; // 0과 1 세기
sum += (long)zero_count*other_count; // 0과 2+ 세기

풀이 코드

import java.util.*;
import java.io.*;
public class Main {
   public static void main(String[] args) throws IOException{
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       int n = Integer.parseInt(br.readLine());
       StringTokenizer st = new StringTokenizer(br.readLine());

       int zero_count = 0;
       int one_count = 0;

       for(int i=0;i<n;i++){
           int input = Integer.parseInt(st.nextToken());
           if(input==0){
               zero_count++;
           }
           if(input==1){
               one_count++;
           }
       }
       int other_count = n-zero_count-one_count;
       long sum = 0;
       sum += (long)(zero_count-1)*(zero_count)/2; // 0 전부 세기
       sum += (long)zero_count*one_count*2; // 0과 1 세기
       sum += (long)zero_count*other_count; // 0과 2+ 세기

       System.out.println(sum);
   }
}