[백준] 14425번 - 문자열 집합

문제

총 N개의 문자열로 이루어진 집합 S가 주어진다.
입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.
• 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.
• 다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.
• 입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

출력

• 첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.

문제 풀이

• 정답은 아래의 체크된 4개의 문자열들이 걸려서 4로 출력되어야 한다.
  

코드 구현

• 배열을 사용할 경우
  → 시간 초과가 발생했다…

(참고) - 찾아보니 배열은 O(n)의 시간이 걸리기 때문에 오류가 났던 것 같다.

• ArrayList
  ArrayList.contains() 호출시 해당 값이 list에 있는지 판단하기 위해 내부적으로 indexOf(object) 메서드를 사용한다. indexOf(object) 메서드는 array 전체를 반복해서 돌고 각각의 element와 비교를 진행함.
  • O(n) 의 시간이 걸림
• HashMap
  HashMap.containsKey(object) 호출시 HashMap구조가 활용됨
  • O(1)의 시간이 걸림

package 문자열알고리즘;

import java.util.HashMap;
import java.util.Scanner;

public class BJ14425 {

    public static void main(String[] args) {
        int N;  // N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.
        int M;  // M개의 줄에는 검사해야 하는 문자열들이 주어진다.

        String str_M;   // 검사해야할 문자열을 저장할 변수
        int ans = 0;    // 정답을 저장할 변수

        // 입력 받기
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        // HashMap 선언
        HashMap<String , Integer> map = new HashMap<>();

        // N개의 줄 입력받기 (집합 S에 포함된 문자열들)
        for (int i=0; i<N; i++) {
            map.put(sc.next(), 0);      // int value는 별로 안필요해서 그냥 0으로 설정하였다.
        }

        // M개의 줄 입력 받으며 검사하기
        for (int i=0; i<M; i++) {
            str_M = sc.next();      // 우선 입력받고

            // 입력 받은게 HashMap 에 존재하는지 검사
            // 해당 key가 존재하지 않으면 null을 리턴하므로 ,
            // str_M이 map안에 있는지는 null값을 갖는지 아닌지로 검사할 수 있다.
            if(map.get(str_M) != null) {
                // null이 아니면 동일한 문자열이 존재한다는 뜻!
                ans++;
            }
        }

        // 정답 출력
        System.out.println(ans);
    }

}

Hashmap 사용법

put()

• put()은 인자로 key와 value를 받습니다.
  전달된 인자는 HashMap에 key-value 관계로 저장이 됩니다.

• public V put(K key, V value)

아래 코드의 HashMap은 key를 String으로, value를 Integer로 사용합니다. 
put()으로 데이터를 저장하였습니다. null은 key, value 모두 허용되며 중복된 key는 마지막에 저장된 값으로 업데이트됩니다.

Map<String, Integer> fruits = new HashMap<>();
fruits.put("apple", 1);
fruits.put("banana", 2);
fruits.put("kiwi", 3);
fruits.put(null, 4);
fruits.put("kiwi", 5);
System.out.println("fruits: " + fruits);

// fruits: {banana=2, null=4, apple=1, kiwi=5}

get()

• get()은 인자로 전달된 key에 해당하는 value를 리턴해 줍니다.
  key가 존재하지 않으면 null을 리턴합니다.

• public V get(Object key) {

다음은 get()으로 value를 가져오는 예제입니다.

Map<String, Integer> fruits = new HashMap<>();
fruits.put("apple", 1);
fruits.put("banana", 2);
fruits.put("kiwi", 3);

System.out.println("get(apple): " + fruits.get("apple"));
System.out.println("get(kiwi): " + fruits.get("kiwi"));
System.out.println("get(undefined): " + fruits.get("undefined"));

// get(apple): 1
// get(kiwi): 3
// get(undefined): null

참고 자료

Java - HashMap 사용 방법 및 예제