[백준 1764] 듣보잡

글에 개요

백준 알고리즘 1764번 "듣보잡" 문제입니다.

백준 알고리즘 분류에서 '구현'에 있는 문제입니다.

이 문제를 처음 접하고 여러가지 문제 해결법이 떠올랐습니다.

저는 그 중 BinarySearch를 활용해서 풀어보기로 결정했습니다. 해당 방법으로 풀면서 몇 가지 문제에 부딪혔는데 이 부분을 핵심 내용에 담아서 알려드리도록 하겠습니다.

[백준 1764] 듣보잡: https://www.acmicpc.net/problem/1764

참고할 글

1. http://brenden.tistory.com/40 ([백준 2577] 숫자의 개수 - 구현 문제)

2. http://brenden.tistory.com/41 ([백준 2839] 설탕 배달 - 구현 문제)

3. http://brenden.tistory.com/42 ([백준 10798] 세로읽기 - 구현 문제)

핵심 내용

※ ArrayList<String> ▶ String[]

String[] ary = new String[list.size()];
ary = list.toArray(ary);

1 2 3

String[] arr1 = list.toArray(new String[list.size()]); String[] arr2 = list.toArray(new String[0]); String[] strings = list.stream().toArray(String[]::new);

cs

: [line 1] 보다 [line 2]가 더 속도가 빠르다고 합니다. (속도 : line2 > line 1)

: [line 3]은 java8에서 사용되는 방법이므로 참고하시기 바랍니다.

1

String[] arr1 = (String[]) list.toArray()

cs

: 여기서는 Object[] 에서 String[]로 cast할 때의 문제가 발생되는 것을 알 수 있습니다.

이는 downcasting하는 과정에서 data를 사용함에 있어 JVM이 잠재적으로 위험한 코드이기 때문에 예방하기 위해 Exception을 발생해줍니다.

※ BinarySearch

Collections.sort(list);
for(int i = 0; i < m; i++) {
    String s = sc.nextLine();
    int index = Arrays.binarySearch(ary, s);
    if(index >= 0) {
        answerList.add(s);
       }
}

: 이진 탐색 알고리즘은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다.

때문에 처음 [line 1]처럼 오름차순으로 sort하고 [line 4]처럼 사용해주시면 됩니다.

This method returns index of the search key, if it is contained in the array, else it returns (-(insertion point) - 1).

여기에서 리턴되는 index 값은 위처럼 되기 때문에, index >= 0 일 때 트리 안에 값이 있는 것입니다.

해결 방법

1. 듣도 못한 사람을 list에 담아줍니다.
2. binary Search를 사용하기 위해 오름차순으로 정렬을 해줍니다.(Collections.sort(list))
3. 트리안에 값이 있을 때 해당 index를 반환하고 값이 있을 경우 answerList에 담아줍니다.
4. 결과를 사전순으로 출력하기 위해 한 번더 오름차순으로 정렬해줍니다.

해결한 코드

백준 참고 내용

듣보잡 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	6062	2313	1638	39.394%

문제

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

입력

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

출력

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

예제 입력 1 

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

예제 출력 1 

2
baesangwook
ohhenrie

힌트