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

문제 링크

---

1. 아이디어

두 배열이 얼마나 유사한지 확인하기 위해 두 배열에 공통으로 포함된 원소의 개수를 구해야 한다. 각 배열의 원소들이 문자열이므로 해시셋을 활용해 한쪽 배열의 모든 원소를 해시셋에 넣은 후, 다른 쪽 배열의 각 원소들이 해시셋에 포함됐는지 확인하는 방식으로 해결할 수 있다.

---

2. 복잡도

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

($N$ = s1의 길이, $M$ = s2의 길이. Python은 s2도 집합으로 만들어 공간 $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))

두 배열을 모두 집합으로 변환한 후 교집합의 크기를 세는 방식으로 해결했다.

---