[백준 JAVA] 14425 문자열 집합

14425 문자열 집합

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

문제설명

HashMap을 이용한 문자열 집합

접근방식

O(N + M) 선형 시간복잡도

 

상수 시간을 가지는 HashMap에 저장할 문자열은 n개와 m개 이므로

전체 시간 복잡도는 O(n + m) 을 가진다.

문제 조건 분석 과정

 

1. HashMap에 문자열과 문자열 빈도수를 저장한다.

2. 각 문자열을 key로 하고 초기값 0을 가지는 정수를 HashMap에 저장한다.

3. m개의 문자열을 입력받고, 입력받은 문자열이 HashMap에 있으면 count를 증가시킨다

 

사용된 자료구조

• HashMap: 문자열을 key로 하고 해당 문자열의 빈도를 value로 저장하여 확인한다

전체코드

import java.io.*;
import java.util.*;

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Map<String, Integer> map = new HashMap<>(); //문자열과 빈도수 저장

        //n개의 문자열을 입력받아 HashMap에 저장
        for (int i = 0; i < n; i++) {
            map.put(br.readLine(), 0); //각 문자열을 key로 하고 초기값 0을 가지는 정수
        }

        int count = 0;

        //m개의 문자열을 입력받아 Hashmap에 포함된 문자열인지 확인하고 count 증가
        for (int i = 0; i < m; i++) {
            if (map.containsKey(br.readLine())) count++;
        }

        System.out.print(count);
    }
}