[백준] 1764번 듣보잡

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

이 문제는 생각보다 쉬운데 생각보다 까다로웠던 문제였던 것 같다.

처음에 이 문제를 접했을때 List로만 해결하려고 했다.

나중에 안 사실이지만 list.contains의 시간 복잡도는 O(N)이라고 한다.

즉, 내가 짠 코드에서는 n^2이라는 결론이 발생된다.

그래서 시간초과가 발생하였다.

혹시나 하는 마음에 list를 set으로 수정했다. 그랬더니 정답이었다. 처음엔 list와 set이 시간차이가 발생하는줄 알았다.

알고 보니 constains에 있었다.

set.contains의 시간 복잡도는 O(1) 즉, list보다 1/n 만큼 더 빠르다는 이야기가 된다.

이게 문제였다.

그래도 모르니 한 가지 실험을 하였다. 받는것은 list로 받고 contains비교는 set으로 하기로했다.

예상대로 정답으로 책정되었다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		List<String> both = new ArrayList<>();
		
		for (int i = 0; i < n; i++) {
			both.add(sc.next());
		}
		
		Set<String> names = new HashSet<>(both);
		List<String> temp = new ArrayList<>();
		for (int i = 0; i < m; i++) {
			String name = sc.next();
			if (names.contains(name)) {
				temp.add(name);
			} 
		}
		
		Collections.sort(temp);
		System.out.println(temp.size());
		
		temp.stream().forEach(System.out::println);
	
		
	}
	

}

 놀랍게도 이건 AC를 받았다.

list와 set 시간 복잡도

Java Collections – Performance (Time Complexity)

 

 

class Main {
	static int N, M;
	static ArrayList<String> ans;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw =  new BufferedWriter(new OutputStreamWriter(System.out));

		String[] temp = br.readLine().split(" ");
		N = Integer.parseInt(temp[0]);
		M = Integer.parseInt(temp[1]);

		ArrayList<String> arr = new ArrayList<>();
		for(int i=0; i<N; i++)
			arr.add(br.readLine());

		quickSort(arr, 0, arr.size()-1);
		ans = new ArrayList<>();
		for(int i=0; i<M; i++){
			String str = br.readLine();
			if(binarySearch(arr, str)){
				ans.add(str);
			}
		}
		
		bw.write(ans.size() + " ");
		bw.newLine();

		if(ans.size() != 0)
			quickSort(ans, 0, ans.size()-1);
		for(int i=0, len=ans.size(); i<len; i++){
			bw.write(ans.get(i));
			bw.newLine();
		}
		bw.flush();
		bw.close();
		br.close();
	}

	public static void quickSort(ArrayList<String> list, int l, int r){
		int left = l;
		int right = r;
		String pivot = list.get((l+r)/2);

		do{
			while(list.get(left).compareTo(pivot) < 0) left++;
			while(list.get(right).compareTo(pivot) > 0) right--;
			if(left <= right){
				String temp = list.get(left);
				list.set(left, list.get(right));
				list.set(right, temp);
				left++;
				right--;
			}
		}while(left <= right);

		if(l < right) quickSort(list, l, right);
		if(r > left) quickSort(list, left, r);
	}

	public static boolean binarySearch(ArrayList<String> list, String target){
		int left = 0;
		int right = list.size()-1;
		boolean flag = false;
		while(left <= right){
			int mid = (left + right) / 2;
			if(list.get(mid).compareTo(target) > 0)
				right = mid-1;
			else if(list.get(mid).compareTo(target) < 0)
				left = mid+1;
			else{
				flag = true;
				break;
			}
		}
		
		return flag;
	}
}

binarysearch라 

이진 검색을 할 줄은 몰랐는데.. ㅡㅡ;; ㅎㅎ