[Java] 백준(실버-3) 14425번 - 문자열 집합

문제 풀이

---

이 문제는 문자열 배열과 HashMap을 활용하는 두 가지 방식으로 풀어보았다.
요구되는 아이디어는 단순한 편이라고 생각이 들었다.

아이디어 도출

• N개의 문자열을 별도의 집합 S로 저장한다.
• M개의 문자열을 입력받으며 집합 S에 포함되는지 확인한다.

문자열 배열 활용

먼저 단순하게 N개의 문자열을 입력받아 집합 S를 만들고 M개의 문자열을 입력받으며 S에 존재하는지 확인하면 된다.
긴말 없이 바로 코드를 작성해보자.

StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());

String[] arr = new String[N];
for(int i=0; i<N; i++) {
    arr[i] = br.readLine();
}

먼저 N과 M을 공백 기준으로 입력받고 N개의 문자열을 저장할 집합 S, arr 배열을 선언하고 N개의 문자열을 입력받으며 arr에 저장한다.

int cnt = 0;
for(int i=0; i<M; i++) {
    String s = br.readLine();
    for(int j=0; j<arr.length; j++) {
        if(s.equals(arr[j])) cnt++;
    }
}

그리고 M개의 문자열을 입력받으며 입력받은 문자열이 arr에 존재하는지 이중 for문으로 검증하여 카운트를 세면 된다.

HashMap 활용

문자열 배열을 활용하여 정답을 내었지만 문제에서 HashMap을 활용하라고 적혀있었기에 HashMap으로도 풀어보았는데, 훨씬 빠른 실행시간을 보여주었다.
HashMap을 활용한 코드를 작성해보자.

StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());

HashMap<String, Integer> hm = new HashMap<>();
for(int i=0; i<N; i++) {
    hm.put(br.readLine(), 0);
}

N과 M을 입력받고 N개의 문자열을 키로, 값을 카운트인 0으로 하여 HashMap을 선언하고 초기화한다.

int cnt = 0;
for(int i=0; i<M; i++) {
    String s = br.readLine();
    if(hm.containsKey(s)) cnt++;
}

그리고 M개의 문자열을 입력받으며 HashMap에 키값으로 존재하는 문자열인지를 확인하고 카운트를 세면 된다.

실행 결과

문자열 배열에서는 이중 for문을 사용하여 O(n^2)이었지만, HashMap을 활용하면 하나의 for문만을 사용하면 되기에 O(n)의 시간복잡도를 가질 수 있어 훨씬 빠름을 알 수 있었다.

실제로 실행시간을 비교해보면 문자열 배열을 활용한 풀이는 2636 ms의 시간이 걸렸지만 HashMap을 활용하니 420 ms로 훨씬 더 빠르다.

작성코드

작성코드 - 문자열 배열 활용

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        String[] arr = new String[N];
        for(int i=0; i<N; i++) {
            arr[i] = br.readLine();
        }

        int cnt = 0;
        for(int i=0; i<M; i++) {
            String s = br.readLine();
            for(int j=0; j<arr.length; j++) {
                if(s.equals(arr[j])) cnt++;
            }
        }
        bw.write(cnt+"\n");

        bw.flush();
        bw.close();
        br.close();
    }   
}

작성코드 - HashMap 활용

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        HashMap<String, Integer> hm = new HashMap<>();
        for(int i=0; i<N; i++) {
            hm.put(br.readLine(), 0);
        }

        int cnt = 0;
        for(int i=0; i<M; i++) {
            String s = br.readLine();
            if(hm.containsKey(s)) cnt++;
        }
        bw.write(cnt+"\n");

        bw.flush();
        bw.close();
        br.close();
    }   
}

회고

• 문자열 배열을 활용한 풀이도 정답이었지만, HashMap을 활용해 반복문을 하나 줄이고 더 빠른 성능의 풀이을 낼 수 있었다.