[2024] 3/9 Leetcode Daily Challenge 2540. Minimum Common Value

2540. Minimum Common Value

코드

해설

sorted in non-decreasing order

다음은 문제 구문 중 일부를 발췌한 것이다. 각 배열을 오름차순 정렬로 제시하고 있다.
앞으로 설명할 코드 로직은 반드시 오름차순 정렬이라는 가정 하에서만 제대로 동작한다.

 while i1 < len(nums1) and i2 < len(nums2):

두 배열의 요소를 비교하는 것이므로, 두 배열 중 더 짧은 길이의 배열 순회가 끝나면
더 이상 비교할 배열의 요소가 없으므로 while문을 탈출한다.

두 배열의 요소가 다음과 같다고 가정해보자.

nums1:[1,2,3]
nums2:[3,4]

i1과 i2는 첫번째 배열 요소의 index인 0으로 초기화해주었다.
이에 각 배열의 요소를 가져오게 되면,

nums1[0] = 1
nums2[0] = 3

이 된다.
이 때 각 배열은 오름차순 정렬이므로 num2의 다음 요소는 무조건 3보다 큰 수가 올 수 밖에 없다.
배열 요소 중 공통 요소의 최소 값을 찾는 과정이므로 num1의 다음 배열 요소를 확인해서 3인 요소가 있는지 찾아야 한다.
그러므로 첫번째 배열의 인덱스를 뜻하는 i1에 +1을 해줘서 그 다음 요소와 비교를 해봐야 한다.

nums1[1] = 2 # i1 + 1
nums2[0] = 3

두 배열 요소가 같지 않고, nums1의 배열 요소의 숫자가 더 작으므로 이번에도 i1에 +1을 해준다.

nums1[2] = 3 # i1 + 1
nums2[0] = 3

두 요소의 숫자가 같으므로 Output으로 3이 return 된다.

if nums1[i1] < nums2[i2]:
	i1 += 1
elif nums1[i1] > nums2[i2]:
	i2 += 1

이처럼 두 요소를 비교하여 더 작은 요소를 가진 배열의 index에 +1을 해주어서 같은 값이 나올 때 까지 순회를 돌리도록 한다.

else:
	return nums1[i1]

두 요소의 숫자가 같다면 해당 값을 return 해주도록 한다.

If there is no common integer amongst nums1 and nums2, return -1.

다음은 문제의 일부를 발췌한 것이다.
공통되는 값이 없으면 -1을 return 하라고 제시하고 있다.

return -1

while문을 돌리면서 값을 return 하지 못할 경우 배열 요소가 공통되는 값이 없다는 뜻이므로
while문을 탈출하여 -1을 return 하도록 한다.

알고리즘

• 투포인터(Two pointer)

시간 복잡도

O(n)