99클럽 코테 스터디 16일차 TIL [04/21]

[시작]

참여 기간 : 2025/03/31 ~ 2025/04/28

참여 난이도 : 파이썬 / 비기너

본 글에서 다룬 문제 : leetcode(349. Intersection of Two Arrays)

벌써 끝나가서 아쉽다... 특강도 끝이라니

다음에 참가할 땐 미들러의 실력을 갖춰서 돌아오겠다.

비기너분들 발표와 TIL을 봤는데 같은 비기너가 아니었음.

나는 비기너 아래 아이언 티어 만들어서 거기 들어가야 한다....

 

 

 

 

[오늘의 문제]

 

[문제 해석]

두 정수 배열 num1과 num2가 주어지는데, 두 배열에 모두 등장하는 교집합 원소들을 모아 배열로 반환해라고 한다.

결과 배열에는 중복 없이 한 번씩만 포함해야 하고

순서는 상관없으니 아무 순서로 반환해도 된다라고 되어있다.

보자마자 어떻게 풀어야 할지 생각나서 딱히 구현에 고민을 하지 않아도 될 듯

바로 코드를 작성해서 돌려보겠다.

 

 

 

[구현]

보자마자 어떻게 풀어야 할지 생각나서 딱히 구현에 고민을 하지 않아도 될 듯

바로 코드를 작성해서 돌려보겠다.

 

 

 

[코드]

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

먼저 set(nums1), set(nums2)를 통해 각 리스트의 중복된 원소를 한 번에 제거해서 집합(set)으로 만든다.

 

그다음 & 연산자를 사용해 두 집합의 교집합만 뽑아낸다.

A에도 있고 B에도 있는 원소들만 뽑아서 새 집합으로 만들기 때문에

문제에서 요구하는 unique(공통된) 원소만 아주 깔끔하게 뽑을 수 있다.

 

마지막으로 list()를 이용해서 집합 안에 들어 있는 값들을 리스트로 변환한다.

문제에서는 순서 상관없다고 했으니 그대로 반환하면 끝!

 

 

 

[제출 결과]

O(n+m)

 

 

 

[다른 접근 방법]

이분탐색으로 문제를 푼다면 코드는 다음과 같다.

from bisect import bisect_left

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums2.sort()                  
        seen, res = set(), []
        for x in nums1:               # nums1을 한 번 순회
            if x in seen:             # 중복 검사해야겠지?
                continue
            seen.add(x)
            i = bisect_left(nums2, x)      # nums2에서 x가 들어갈 위치 탐색함
            if i < len(nums2) and nums2[i] == x:
                res.append(x)        # 값이 일치하면 교집합에 추가함
        return res

시간복잡도

O(mlogm+nlogm)

 

 

 

[회고]

사실 이분 탐색으로 풀어라는 강제적인 조건(예를 들면 시간복잡도가 이 정도 나와야 한다)이 있었으면

바로 이분탐색을 시도했을 텐데, 쉽게 쉽게 풀고 싶어서 시도했더니 풀렸다.

사실 이분탐색으로 풀어야 하는 문제였다 ㅎㅎ; (머쓱)

어쩐지 오늘 보너스 문제가 이분탐색 문제를 주시더니...

오늘의 문제를 풀지 않은 상태로 보너스 문제로 이분탐색을 먼저 접해버려서 뭐가 이상하다 생각했다.

암튼 이분탐색으로도 잘 풀었음