[Java] 백준 1764 듣보잡 - 실버4

https://www.acmicpc.net/problem/1764

1764번: 듣보잡

 

 

생각

• 듣도 못한 사람 - A그룹 / 보도 못한 사람 - B그룹
• 듣도 보도 못한 사람 - A U B (합집합)

A그룹을 해시에 저장하고 B그룹 사람 이름의 key값이 존재하는지 확인, 존재하면 count ++

 

 

 

시간복잡도?

정렬된 값으로 저장하는 것보다 해시가 가장 빠르다고 생각함. 실험을 통해 알아보자!

 

 

1. 배열

HashMap을 사용하지 않으면 시간초과남

 

2. HashMap 사용하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

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

    int noListen = Integer.parseInt(st.nextToken());
    int noLook = Integer.parseInt(st.nextToken());
    List<String> list = new ArrayList<>();

    HashMap<String, String> hash = new HashMap<>();

    for (int i =0; i<noListen; i++)
      hash.put(br.readLine(), "a");

    for (int i =0; i<noLook; i++) {
      String name = br.readLine();

      if (hash.get(name) != null)
        list.add(name);
    }

    Collections.sort(list);

    StringBuilder sb= new StringBuilder();
    sb.append(list.size());

    for (String name: list) {
      sb.append("\n");
      sb.append(name);
    }

    System.out.println(sb);
  }
}

• HashMap밖에 몰라서 이거 씀
• 필요없는 값 ("a")를 저장해야해서 불편했음

 

3. HashSet

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

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

    int noListen = Integer.parseInt(st.nextToken());
    int noLook = Integer.parseInt(st.nextToken());
    List<String> list = new ArrayList<>();

    HashSet<String> arr = new HashSet<>();

    for (int i =0; i<noListen; i++)
      arr.add(br.readLine());

    for (int i =0; i<noLook; i++) {
      String name = br.readLine();

      if (arr.contains(name))
        list.add(name);
    }

    Collections.sort(list);

    StringBuilder sb= new StringBuilder();
    sb.append(list.size());

    for (String name: list) {
      sb.append("\n");
      sb.append(name);
    }

    System.out.println(sb);
  }
}

• HashMap에 다른 값을 저장해야하는 게 불편해서 구글링 한 결과 HashSet이라는 게 있는 걸 확인
• HashMap과 비슷한 성능을 보인다

 

 

 

 

 

 

 

도움자료(HashSet)

https://velog.io/@yanghl98/%EB%B0%B1%EC%A4%80-1764-%EB%93%A3%EB%B3%B4%EC%9E%A1-JAVA%EC%9E%90%EB%B0%94

[백준] 1764 : 듣보잡 (JAVA/자바)