문제 이해

듣지 못한 사람 N명이 나오고, 보지 못한 사람 M명이 나온다.
이 때 듣지도 못했고 보지도 못했던 사람을 고르는 문제이다.

즉, 2개의 String 배열이 주어지고, 2개 배열에 동시에 존재하는 사람을 찾아 출력한다
이 때 2개 배열에 동시에 존재하는 사람을 사전순으로 출력한다.

문제 풀이

이전에 풀었던 수 찾기의 String 버전이다.
따라서 먼저 나온 N명의 듣지 못한 사람을 배열에 저장할 것이다.
이후 보지 못한 사람을 한 명씩 입력받고, 해당 사람 이름이 배열에 존재하는지 여부를 확인하면 될 것이다.

이 때, left와 right를 어떻게 해야할지 생각해야 한다.
String 배열을 Arrays.sort로 Sorting할 경우 (ASCII코드 기준) 사전 순으로 정렬된다.

A.compareTo(B) 값의 결과는 아래와 같다.

1. A가 사전순으로 B보다 앞이다 : 음수
2. A와 B가 같다 : 0
3. A가 사전순으로 B보다 뒤다 : 양수

내가 찾고 싶은 문자열이 A일 경우, B.compareTo(A) > 0 라면 B가 A보다 사전순으로 뒤에 있다는 의미이므로 B가 존재하는 index 이전 위치만 찾으면 된다. 즉 right값을 변경해준다.

음수일 경우 반대이므로, left 값을 변경해준다.

코드

import java.util.*;

public class Main {
	static int N;
	static String[] arr;
	
	static Boolean bin_search(String str) {
        // 이분 탐색 함수
		int left = 0;
		int right = N -1;
		int mid;
		while(left <= right) {
			mid = (left + right) / 2;
			
			if(arr[mid].compareTo(str)>0) {
             // arr[mid]가 str보다 뒤에 존재함
             // mid보다 왼쪽만 Search하면 되기 때문에 right = mid - 1로 설정
				right = mid - 1;
			}
			else if(arr[mid].compareTo(str)<0) {
            // arr[mid]가 str보다 앞에 존재함
            // mid보다 오른쪽만 Search하면 되기 때문에 left = mid + 1로 설정
				left = mid + 1;
			}
			else {
                // str과 똑같은 값이 array에 존재함
                // True를 반환 후 함수 종료
				return true;
			}
		}
        // while문을 빠져나왔다는 의미는 str과 똑같은 값이 array에 
        // 존재하지 않음을 의미한다. 따라서 False를 반환한다.
		return false;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		int M = sc.nextInt();
		arr = new String[N];
		sc.nextLine();
		
		for(int i = 0;i<N;i++) {
			arr[i] = sc.nextLine();
		}
		Arrays.sort(arr); // 이분 탐색의 핵심 : 배열의 Sorting!!!
		
		String str;
		StringBuilder sb = new StringBuilder();
		String[] ans = new String[N];
		int answer = 0;

		for(int i =0;i<M;i++) {
			str = sc.nextLine();
			
			if(bin_search(str)) {
                // bin_search(str) = true일 경우 해당 값이 배열에 
                // 존재한다는 의미이다. 배열에 이름 저장 & 개수 1 증가시킨다
				ans[answer] = str;
				answer++;
			}
		}

		Arrays.sort(ans, 0, answer);
        // 2개 배열에 동시에 존재하는 값을 정렬한 이후 출력해야 한다.
        // 0 ~ (answer-1) index 공간에만 이름이 저장되어 있기 때문에 
        // 이 부분만 Sorting 시킨다.
		
		sb.append(answer+"\n");
		for(int i=0;i<answer;i++) {
			sb.append(ans[i]+"\n");
		}
		System.out.println(sb);
	}
}

결과

• 시간 초과 : 이분 탐색을 사용하지 않고 JAVA에 존재하는 contains() 메서드를 통해 문제를 풀어 보려고 하였다. 내가 직접 구현하는 것보다 효율적이지 않을까 기대했지만, 아니였다. contains() 명령도 Brute-Force와 비슷하다고 생각해야 할 것 같다.
• 5번째 틀렸습니다 : 이름을 출력할 때 Sorting을 하지 않아 발생하였다.
• 2 ~ 4번째 틀렸습니다 : 5번째 틀렸습니다 이유를 내가 String의 compareTo를 잘못 이해하였다고 착각하여 코드를 고쳐 생긴 문제였다. 결과적으로 내가 처음 생각했던 compareTo 개념으로 코드를 고치니 통과하였다. 내가 가지고 있는 JAVA 메서드에 대한 개념에 대해 자신감을 가져야 할 것 같다.