문제

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

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

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

BOJ1764

접근

두 그룹의 문자열을 각각 A배열과 B배열에 저장한 뒤, 같은 문자열이 존재하는지 검사하는 문제다. 여러 풀이 중 정렬한뒤 비교하는 방법을 사용했다.

각 배열을 사전순으로 정렬한 뒤, 각 배열을 탐색하는 현재위치를 지정한다. 각 배열의 위치에 해당하는 문자열을 비교한 뒤, 같으면 두 배열 모두 현재위치를 +1, 다르다면 작은 쪽의 위치를 +1 시킨다. 한쪽 배열이라도 탐색이 끝났다면 종료한다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// 입력
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		String [] hear = new String[n];
		String [] see = new String[m];
		
		
		String [] result = new String[Math.max(n,m)]; // 같은 문자열이 들어갈 배열
		int count = 0; // 같은 문자열의 개수
		
		for(int i = 0; i < n; i++)
			hear[i] = sc.next();
		for(int i = 0; i < m; i++)
			see[i] = sc.next();
		
		// 정렬
		Arrays.sort(hear);
		Arrays.sort(see);
		
		// i는 hear 배열의 현재위치. j는 see 배열의 현재위치.
		int i = 0, j = 0;
		
		// 문자열이 같다면 result 배열에 저장 후 현재위치를 모두 증가시키기.
		// 문자열이 다르다면 사전순으로 작은쪽의 현재 위치를 증가시키기.
		while(i != n && j != m) {
			if(hear[i].compareTo(see[j]) > 0) {
				j++;
			}
			else if(hear[i].compareTo(see[j]) < 0) {
				i++;
			}
			else {
				result[count++] = hear[i];
				i++;
				j++;
			}
		}
		
		// 출력
		System.out.println(count);
		for(i = 0; i < count; i++)
			System.out.println(result[i]);
	}

}