[2024] day 70. Leetcode 2540. Minimum Common Value

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 9일 (토)
Leetcode daily problem

2540. Minimum Common Value

https://leetcode.com/problems/minimum-common-value/description/?envType=daily-question&envId=2024-03-09

Problem

오름차순으로 정렬된 두 개의 정수 배열 nums1, nums2 가 각각 주어 질 때 두 배열의 원소 중 가장 작은 공통이 되는 원소의 값을 반환하고,
만약 공통이 되는 원소가 없다면 -1을 반환한다.

Solution

two pointer

두 배열을 set으로 해서 set 자료구조에서 제공하는 intersection에서 min 함수로 찾으면 time limit이 난다.
해결 방법은 two pointer 를 사용하는 것이다.

주어진 배열 nums1, nums2의 각각의 시작 포인터를 두고
두 배열을 포인터로 이동시켜나가면서 공통된 가장 작은 원소를 찾는다.

반복문을 사용해서 포인터를 이동시켜 나가야 하는데
조건은 두 배열의 크기가 다르기 때문에 각 배열을 도는 포인터들이 배열의 크기에 넘어가면 반복을 멈춰야 하는 것이다.

가장 작은 크기의 배열을 한 번 탐색했음에도 불구하고 공통원소가 없으면 -1을 반환하도록 한다.

Code

class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        start1, start2 = 0, 0

        while start1 < len(nums1) and start2 < len(nums2):
            if nums1[start1] < nums2[start2]:
                start1 +=1
            elif nums1[start1] > nums2[start2]:
                start2 +=1
            else:
                return nums1[start1]
        return -1

Complexicity

시간 복잡도

두 배열을 한 번씩 탐색하기 때문에, 시간 복잡도는 O(min(n,m))이다.
n : num1 의 길이, m : num2의 길이

공간 복잡도

포인터에 상수만 할당해서 순환하므로 공간복잡도는 O(1)이다.