[Programmers] #120903 - 배열의 유사도 [Java][C++][Python]

문제 링크

---

1. 아이디어

한쪽 배열의 원소를 해시 집합에 넣은 뒤 다른 배열을 순회하며 집합에 포함되는 원소의 개수를 센다. 두 배열 모두 원소가 중복되지 않으므로 이 개수가 곧 공통 원소의 개수다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N + M)$	$O(N)$

($N$ = s1의 길이, $M$ = s2의 길이. Python 풀이는 두 배열을 모두 집합으로 만들어 공간이 $O(N + M)$이다)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {
    public int solution(String[] s1, String[] s2) {
        Set<String> seen = new HashSet<>(List.of(s1));
        int cnt = 0;

        for (String s : s2) {
            if (seen.contains(s)) cnt++;
        }

        return cnt;
    }
}

#include <bits/stdc++.h>
using namespace std;

int solution(vector<string> s1, vector<string> s2) {
    unordered_set<string> seen(s1.begin(), s1.end());
    int cnt = 0;

    for (string& s : s2) {
        if (seen.contains(s)) cnt++;
    }

    return cnt;
}

def solution(s1, s2):
    return len(set(s1) & set(s2))

---