[SWEA] 2948 문자열 교집합 - JAVA

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV-Un3G64SUDFAXr 

SW Expert Academy

개인적으로 이게 왜 D3인지 의문이다.

 

문제풀이

n과 m이 10만이하이고 자바의 시간제한은 8초로 단순히 이중반복문을 사용하면 시간초과가 날 것이다

따라서 중복되는 값이 있는지 체크하기 위해서 n집합을 HashSet에 넣어두고 m집합 요소들이 HashSet에 포함되는지 체크하면 된다.

HashSet에서 탐색은 O(1)로 동일값이 있는지 확인하는데 효율적이기 때문에 매우 효율적이다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

class Solution
{
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());


        for(int test_case = 1; test_case <= T; test_case++)
        {
            Set<String> set = new TreeSet<>();
            int cnt = 0;
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                set.add(st.nextToken());
            }

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < m; i++) {
                if (set.contains(st.nextToken()))
                    cnt++;
            }

            sb.append("#" + test_case + " " + cnt + "\n");
        }
        System.out.println(sb);
    }
}