[백준/Java] 1764 듣보잡

조건

1. 듣도 못한 사람의 수 N 보도 못한 사람의 수 M 이 주어진다

2. 그 후에 듣도 못한 사람의 이름과 보도 못한 사람의 이름이 입력된다

3. 한줄에 한명의 이름만 입력되고 소문자이다.

4. 겹치는 사람의 수와 이름들을 출력한다.

입력예제

해설

이름의 띄어쓰기가 없으니 한줄 씩 읽어 데이터를 넣으면 될 것이고 길이가 20이하이기에 변수 type은 String을 사용한다

가장 쉽게 할 수 있는 방법은 N * M 일것이다. 물론 이렇게 한다면 N과 M의 최대 수가
500,000이기 때문에 2500억이 나오기 때문에 시간 초과가 발생한다.

그렇기에 처음 받는 듣도 못한 사람을 입력받고 오름차순으로 sort후 이분탐색을 실시할 것이다. 앞의 내용을 코드화 한다면

코드

import java.io.*;
import java.util.*;

public class Main {
	
	
	static int N,M;
	static String[] A,B;
	
	static FastReader scan = new FastReader();
	static StringBuilder sb = new StringBuilder();
	
	static void input() {
		N = scan.nextInt(); // 듣도 못한 사람의 수
		M = scan.nextInt(); // 보도 못한 사람의 수 
		A = new String [N + 1]; // 배열의 Index시작을 1로 하기위해 +1 
		B = new String [M + 1]; 		
		for(int i=1;i<=N;i++) {
			A[i] = scan.nextLine(); //듣도 못한 사람의 이름 넣기
		}
		
	
	}
	static boolean findAns(String[] A, int L, int R,String x) {
		 while (L <= R){ // 이분탐색 실행 
	            int mid = (L+R)/2;
	            if (A[mid].equals(x)) // String의 값들이 같다면 true반환
	                return true;

	            if (A[mid].compareTo(x) < 0)
	                L = mid + 1;
	            else
	                R = mid - 1;
	        }
	        return false; // 공통된 이름이 없다면 false 반환
	}
	
	static void find() {
		Arrays.sort(A,1,N + 1); // 듣도 못한 사람배열을 오름차순으로 정렬
		
		int index = 0; // index값을 위한 int 변수
		for(int i=1;i<=M;i++) {
			String ans = scan.nextLine(); // 보도 못한 사람의 이름 받기
			if(findAns(A,1,N,ans)) { // findAns에 듣도 못한 사람 배열과 시작 인덱스 , 끝 인덱스 , 비교할 보도 못하 사람의 이름을 파라미터로 넣기 
			B[++index] = ans; // B 배열에 넣어준다.
			}
		}
		Arrays.sort(B,1,index + 1);// 이름출력을 오름차순으로 하기 위해 sort
		sb.append(index).append('\n'); // 배열의 크기가 곧 겹치는 사람의 수
		for(int i = 1;i <= index;i++ ) {
			sb.append(B[i]).append('\n'); // 정렬된 배열에서 데이터를 받아와 sb에 넣기 
		}
		System.out.println(sb);
	}


	public static void main(String[] args) {
		// TODO Auto-generated method stub
	input();
	find();
	}
	
	static class FastReader {
	BufferedReader br;
	StringTokenizer st;
	
	public FastReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
		}
	
	public FastReader(String s) throws FileNotFoundException {
		br = new BufferedReader(new FileReader(new File(s)));
		}
	
	
	String next() {
		while(st == null || !st.hasMoreElements()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch(IOException e) {
				e.printStackTrace();
			}
		}
		return st.nextToken();
		}
	
	int nextInt() {
		return Integer.parseInt(next());
	}
	long nextLong() {
		return Long.parseLong(next());
	}
	
	double nextDouble() {
		return Double.parseDouble(next());
	}
	
	String nextLine() {
		String str= "";
		try {
			str = br.readLine();
		} catch(IOException e) {
			e.printStackTrace();
		}
		return str;
		}
	}

}