14425번 : 문자열 집합

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

14425번: 문자열 집합

 

 

문제

 

 

코드

HashSet 사용 X

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

public 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 []s = new String[n];
        for(int i=0;i<n;i++) {
            s[i] = br.readLine();
        }
        String[] arr = new String[m];
        for(int i=0;i<m;i++) {
            arr[i] = br.readLine();
        }
        int count=0;
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(s[j].equals(arr[i])) {
                    count++; break;
                }
            }
        }
        bw.write(count+""); bw.flush();
    }
}

HashSet 사용 O

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

public 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());

        HashSet<String> set = new HashSet();
        for(int i=0;i<n;i++) {
            set.add(br.readLine());
        }
        int count=0;
        for(int i=0;i<m;i++) {
            String s = br.readLine();
            if(!set.add(s)) count++;
            else set.remove(s);
        }
        bw.write(count+""); bw.flush();
    }
}

 

 

해결방법

처음 문제를 풀 땐 Set을 생각하지 못하고 배열로 풀었다. 이 방법도 맞긴 하지만 시간을 타이트하게 준다면 틀렸을 것이다. 두 번째 방법으로 HashSet을 사용하여 풀었는데 훨씬 속도가 빨랐다. 이때 유의할 점은 M개의 문자열 중에 중복되는 문자열이 있을 수 있으므로 M개의 문자열 중에 HashSet에 저장된 문자열은 카운팅 되지 않도록 바로 삭제해줘야 한다.