[JAVA] 백준 1764번 : 듣보잡

 

- 코드

  - 초기 코드인데, 시간초과가 뜬다.

  - 문제는? 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	static int n, m;
	static String temp;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				
		temp = br.readLine();
		StringTokenizer st = new StringTokenizer(temp);
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		String[] a = new String[n+m];

		for(int i=0;i<n+m;i++) {
			a[i] = br.readLine();
		}

		for(int i=0;i<m;i++) {
			for(int j=0;j<n;j++) {
				if(a[i+n].equals(a[j])) {
					System.out.println(a[i+n]);
					break;
				}
			}
		}
		
	}
}

 

- 마지막 코드

   - String배열 대신 ArrayList와 HashSet을 사용하니 속도가 개선되었다. 출력은 BufferedWriter를 사용했다. 이유는 아래에 정리

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        HashSet<String> a = new HashSet<>();
        ArrayList<String> list = new ArrayList<>();
        
        for(int i = 0; i < n; i++){
            a.add(br.readLine());
        }

	for(int i=0;i<m;i++) {
		String temp = br.readLine();
		if(a.contains(temp))
			list.add(temp);
        }
		
	Collections.sort(list);	
	bw.write(list.size() + "\n");
	for(String temp : list)
		bw.write(temp + "\n");

        bw.flush();
        br.close();
        bw.close();
		
	}
}

 

 

- 정리 

   - 아무리 생각해도 속도를 개선할 방법이 떠오르지 않아서 다른 사람의 코드를 보았다. (다른 점은 HashSet, ArrayList와 BufferedWriter를 사용했다는 것!!)

   - BufferedReader, BufferedWriter, StringTokenizer를 사용하는 이유는 따로 블로그에 정리하였습니다.

   - HashSet과 ArrayList를 쓰면 빨라지는 이유는 HashSet이다. HashSet의 특징은 중복된 값을 허용 X, 순서를 보장하지 않는다. List는 본질적으로 순서를 관리해야 하기 때문에 내부적으로 순서 정보를 알 수 있도록 구현해야 한다. ArrayList도 List 인터페이스를 구현한 클래스이므로, 순서 정보를 관리해야하며, 이를 위해 내부적으로 배열(Array)을 사용하여 구현되어 있다. 그렇기 때문에 상대적으로 시간이 오래걸린다.

 

 반면에, HashSet은 순서를 보장할 필요가 없다. 그러므로 Set에 저장된 무언가를 찾을 때는, 순서와 상관없이 그냥 찾으면 되는 것이므로, 찾는 방법이 List에 비해 자유로울 수 있다. 이때 찾는 속도를 극대화 하기위해 Set을 구현할 때 Hash를 사용한 것이 HashSet이다. Hash로 검색하면 검색 시간이 데이터 크기에 상관없이 일정하게 매우 짧다!!라고 이해하면 될 것 같다.

 

결론 : List를 쓰나 Set을 쓰나 동작에 차이가 없다면 HashSet을 써라!!!