알고리즘 풀이/백준

[백준][Java] 1764번 듣보잡

배게 2018. 5. 16. 12:34
728x90

공부해야 할 것 : binarySerach, Collections .sort , toArray() 메소드, binaryserach에 sorting이 필요한 이유


단순탐색정렬로 시간초과 2번 났음

시간초과가 int때문인줄 알고 long으로 바꿨는데 무의미


탐색시간에 문제가 있었음



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args)  {
		
		 Scanner sc = new Scanner (System.in);
		 
		 long N = sc.nextInt();
		 long M = sc.nextInt();
		 long i;
		 long res=0;
		 
		 ArrayList<String> dd = new ArrayList<String>();
		 ArrayList<String> ddbd = new ArrayList<String>();
		 
		 sc.nextLine();
		 for(i=0;i<N;i++) {
			 dd.add(sc.nextLine());
		 }
		 Collections.sort(dd);
		 String[] ndd = new String[dd.size()]; 
		 ndd=dd.toArray(ndd);
		 
		 String bd;

		 for(i=0;i<M;i++) {
			 bd=sc.nextLine();
			 int idx = Arrays.binarySearch(ndd, bd);
			 
			 if(idx>=0) {
				 ddbd.add(bd);
				 res++;
			 }
		 }
		 Collections.sort(ddbd);
		 
		 System.out.println(res);
		 for (String string : ddbd) {
			System.out.println(string);
		}
	}
}