[백준]1764 - 듣보잡 문제 풀이(Java,자바)

풀이

코드

public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = reader.readLine().split(" ");
        int n = Integer.parseInt(inputs[0]);
        int m = Integer.parseInt(inputs[1]);

        HashSet<String> dontListenPeople = new HashSet<>();
        Set<String> result = new TreeSet<>();

        for (int i = 0; i < n; i++) {
            dontListenPeople.add(reader.readLine());
        }

        for (int i = 0; i < m; i++) {
            String name = reader.readLine();
            if (dontListenPeople.contains(name)) {
                result.add(name);
            }
        }
        System.out.println(result.size());
        for (var i : result) {
            System.out.println(i);
        }
    }

풀이법

이 문제는 Set 자료구조를 사용하면 쉽게 풀 수 있다.

먼저, 듣도 보도 못한 사람들은 찾기 위해 HashSet을 사용한다.

HashSet은 전체적인 특징은 다음과 같다.

 

• 중복을 허용하지 않음
  • HashSet은 동일한 객체(혹은 값)를 여러 번 저장할 수 없다. 중복된 값이 추가되려 하면 무시된다.
  • 중복 여부는 equals() 메서드와 hashCode() 메서드로 판단한다.
• 순서가 보장되지 않음
  • HashSet은 내부적으로 해시 테이블을 사용하기 때문에 요소가 저장되는 순서를 보장하지 않는다.
  • 삽입 순서가 중요한 경우, LinkedHashSet을 사용할 수 있다.
• 빠른 검색, 추가, 삭제
  • 해시 기반 자료구조이므로 평균적으로 **O(1)**의 시간 복잡도로 검색, 추가, 삭제 작업을 수행할 수 있다.
• null 값 허용
  • 하나의 null 값만 허용된다.

문제에서 중복을 배제하고 있기 때문에 HashSet의 사용은 매우 적절하다고 할 수 있다.

듣도 못한 사람들을 먼저 HashSet에 넣고 보도 못한 사람들을 탐색할 때, 바로 HashSet에 contain 함수로 있는지 파악한다.

 

문자열의 사전 정렬

영문자 기준으로 String을 Array에 넣으면 Array.sort를, Collections에 넣었으면 Collections.sort를 사용하면 오름차순으로 정렬된다.

이때, 정렬이 진행되는 건 유니코드 기반으로 처리된다.

 

만약, 내림차순으로 처리하고 싶다면 Comparator를 만들어주면 된다.

Collections.sort(list, Collections.reverseOrder());

 

영문자말고 한국어는 사전순으로 어떻게 정렬할까?

import java.text.Collator;
import java.util.Locale;


Collator collator = Collator.getInstance(Locale.KOREAN);
Collections.sort(list, collator);
Collections.sort(list, collator.reversed());

 

자바에선 다국어 정렬을 위해 Collator라는 객체를 제공한다. 이 인스턴스를 불러서 sort를 하면된다.

java 1.1 버전부터 있으니 웬만한 코테에서 다 사용할 수 있을 것이다.