AtCoder Beginner Contest 154 C - Distinct or Not

問題

atcoderサイト

提出1回目(NG)

「この整数列のどの 2つの要素も互いに異なる」とあるので、入力された値をリストに保存し、すでにリストに登録された値が入力されたら"NO"を出力すればよいのではないか

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Long> c = new ArrayList<>();
        for(int i=0;i<n;i++){
            long a = sc.nextLong();
            if(c.contains(a)){
                System.out.println("NO");
                return;
            }else{
                c.add(a);
            }
        }
        sc.close();
        System.out.println("YES");
    }
}

結果はTLE

原因を考える

Nが最大200000件 入力するたびに"contains"を行っているのが影響しているのではないか java.util.contaisは内部でindexOf()で検索を行っている indexOf()はリストのサイズ分forループを回しているため、常に入力1回×リストのサイズの処理が行われていることになる contaisのソースコード参考

提出2回目(OK)

java.util.Listではなくjava.util.Setを使用する Listは重複を許容しないが、Setは重複を許容する そのため、"入力件数とSetのサイズが一致しない"場合、"NO"を出力すればよい

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<Integer> c = new HashSet<>();
        for(int i=0;i<n;i++){
            c.add(sc.nextInt());
        }
        sc.close();
        if(n==c.size()){
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
    }
}

結果はAC

GitHub

なしてSetが思いつかないかなぁ。。。