(문자열) (JAVA) 1764 듣보잡

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));
    StringTokenizer st = new StringTokenizer(br.readLine()," ");

        
       int N = Integer.parseInt(st.nextToken());
       int M = Integer.parseInt(st.nextToken());
       List<String> list= new ArrayList<>();;
       List<String> list2= new ArrayList<>();;
     
    
        for(int i=0;i<N;i++){
        list.add(br.readLine());
       }//듣도 못한 사람 list에 입력 

    for(int j=0;j<M;j++){
         String M1 = br.readLine();
         if(list.contains(M1)){
         list2.add(M1);
        }
    }
    System.out.println(list2.size());
    Collections.sort(list2);
    
    for(String a : list2){
        System.out.println(a);
    }

}
}

- 로직은 맞지만 시간초과가 발생한 코드 

 

 

 

 

 

 

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));
    StringTokenizer st = new StringTokenizer(br.readLine()," ");

        
       int N = Integer.parseInt(st.nextToken());
       int M = Integer.parseInt(st.nextToken());
       Set<String> set= new HashSet<>();
       List<String> list= new ArrayList<>();
     
    
        for(int i=0;i<N;i++){
        set.add(br.readLine());
       }//듣도 못한 사람 list에 입력 

    for(int j=0;j<M;j++){
         String M1 = br.readLine();
         if(set.contains(M1)){
         list.add(M1);
        }
    }
    System.out.println(list.size());
    Collections.sort(list);
    
    for(String a : list){
        System.out.println(a);
    }

}
}

- 성공코드 

- HashSet과 ArrayList의 contains() 메서드의 시간복잡도 차이는 O(1) , O(n) , 

- ArrayList는 인덱스를 전부 검사하면서 같은 값이 있는지 비교하지만 

- HashSet은 내부적으로 HashSet은 HashMap Instance를 구현하고 있고 contains() 메서드를 호출하게되면 HashMap.containsKey(object)가 호출된다고 보면 된다