[Java] 백준 1764번 - 듣보잡

문제

---

•  문제
  • 링크 : https://www.acmicpc.net/problem/1764
  • 듣도 보도 못한 사람의 명단 구하기

 

• 조건
  • 1 ≤ N ≤ 500,000
  • 1 ≤ M ≤ 500,000
  • 듣도 못한 사람들 중에 중복된 사람 X
  • 보도 못한 사람들 중에 중복된 사람 X

 

• 입력
  • 첫번째 줄
    • N M : N - 듣도 못한 사람 수, M - 보도 못한 사람 수
  • 2 ~ (N+1)번째 줄
    • 듣도 못한 사람들의 이름
  • (N+2) ~ (N+M+2)번째 줄
    • 보도 못한 사람들의 이름

 

• 출력
  • 듣도 보도 못한 사람의 수와 이름을 알파벳 순으로 출력하기

 

코드

---

• 로직 1)
  • Map 이용해서 풀기

package backjoon;

import java.util.*;

// 듣보잡
public class No1764 {
    public static void main(String[] args) {
        // Map 사용
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

       Map<String, Integer> map = new HashMap<>();
       List<String> list = new ArrayList<>();

       while(N-->0) {
           map.put(sc.next(), 1);
       }
       while(M-->0) {
           String name = sc.next();
           map.put(name, map.getOrDefault(name,0) +  1);
           if(map.get(name) == 2) list.add(name);
       }

       System.out.println(list.size());
       list.stream().sorted().forEach(System.out::println);
    }
}

 

• 로직 2)
  • Set 이용해서 풀기

package backjoon;

import java.util.*;

// 듣보잡
public class No1764 {
    public static void main(String[] args) {
        // Set 사용
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        Set<String> set = new HashSet<>();
        List<String> list = new ArrayList<>();

        while(N-->0) {
            set.add(sc.next());
        }
        while(M-->0) {
            String name = sc.next();
            if(set.contains(name)) list.add(name);
        }

        System.out.println(list.size());
        list.stream().sorted().forEach(System.out::println);
    }
}

 

주의할 점 & 통과여부

---

• 주의할 점
  • 처음에 Map과 Set이 아닌 List(ArrayList)를 구현해서 풀었지만 시간초과 발생
    • 원인 : 시간 복잡도 고려 X
    • List의 Contains()는 시간 복잡도가 O(N)이기 때문에 시간 초과 발생
    • 자세한 시간복잡도는 아래 링크 참고
      • https://us-study.tistory.com/186

 

• 통과여부
  
  • 성공

 

• 참고 사이트
  • 시간 복잡도 : https://www.grepiu.com/post/9
  • 시간 복잡도 : https://hbase.tistory.com/185
  • 문제 풀이 : https://propercoding.tistory.com/65