본문으로 바로가기

[백준 1764] 듣보잡

category 알고리즘/백준 알고리즘 2018. 5. 8. 09:31
글에 개요

백준 알고리즘 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[]

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

[참고 링크]

(https://stackoverflow.com/questions/5374311/convert-arrayliststring-to-string-array)


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


1
2
3
4
5
6
7
8
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);
       }
}
cs

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

때문에 처음 [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 MB60622313163839.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

힌트


'알고리즘 > 백준 알고리즘' 카테고리의 다른 글

[백준 2960] 에라토스테네스의 체  (0) 2018.05.09
[백준 2563] 색종이  (0) 2018.05.08
[백준 1764] 듣보잡  (0) 2018.05.08
[백준 10798] 세로읽기  (0) 2018.05.07
[백준 2839] 설탕 배달  (0) 2018.05.06
[백준 2577] 숫자의 개수  (0) 2018.05.06

댓글을 달아 주세요