1764_듣보잡 (JAVA)

1764번: 듣보잡

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		String[] nolisten = new String[n];
		String[] nosee = new String[m];

		for(int i=0; i<n; i++){
			nolisten[i] = br.readLine();
		}
		Arrays.sort(nolisten);
		
        for(int i=0; i<m; i++){
			nosee[i] = br.readLine();
		}
		Arrays.sort(nosee);
		
        
		int cnt = 0;
		StringBuilder sb = new StringBuilder();
		
		for(int i=0; i< nolisten.length; i++){
			if(check(nolisten[i], nosee)){
				cnt++;
				sb.append(nolisten[i]).append('\n');
			}
		}

		System.out.println(cnt);
		System.out.print(sb);
        br.close();
	}

	private static boolean check(String str, String[] nosee){
		int min = 0;
		int max = nosee.length-1;
		int middle;

		while(min<=max){
			middle = (min+max)/2;

			if(str.equals(nosee[middle]))
				return true;

			if(str.compareTo(nosee[middle])<0)
				max = middle-1;
			else
				min = middle+1;
		}

		return false;
	}
}

 

nolisten[] 원소가 nosee[] 에 포함되어 있는지를 하나씩 확인해야 한다.

즉 nosee[]에서 nolisten[]원소를 찾는 것과 같고, 이를 이분탐색으로 구현했다.

 

1. 듣보잡의 명단을 '사전순으로' 출력해야 되기 때문에, nolisten[]과 nosee[]를 미리 정렬해주었다.

 

2. nolisten[] 원소를 하나씩 check()함수를 통해 nosee[]에 속해있는지 찾는다. == 이분탐색

   true리턴 == nosee[]에 포함되어 있다는 것으로, cnt++, sb에 append()해주었다.

   

   - check()함수 과정 (이분탐색)

     1) nosee[]의 모든 원소를 대상으로 str이 포함되어 있는지를 찾는 것이다.

     2) 그러므로 범위는 - nosee[]의 인덱스를 기준으로 설정한다.

        최소값=0, 최대값=nosee.length-1

     3) str.compareTo() > 0 이면, b>a인 경우와 같다. 그러므로 범위의 최소값을 middle+1로 수정

        str.compareTo() < 0 이면, a<b인 경우와 같다. 그러므로 범위의 최대값을 middle-1로 수정

 

 

 

 

 

string.compareTo()

- 스트링의 앞 자리부터 하나씩 비교해서 - 리턴

- 리턴값 : int형 값

   ①  0 : abc == abc

   ②  양수 : zab > aab

   ③  음수 : aab < zab