[2024] Day22. 645. Set Mismatch

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

2024년 1월 22일 (월)
Leetcode daily problem

645. Set Mismatch

https://leetcode.com/problems/set-mismatch/description/?envType=daily-question&envId=2024-01-22

Problem

1부터 n까지의 길이로 구성되어 있는 배열에서
중복된 값, 결측 값이 있을 때 해당 배열에서 중복된 원소와 결측원소를 찾아서 반환하는 문제이다.

Solution

data structure

n의 길이만큼의 배열을 생성하고(tmp) , 주어진 정수가 담긴 배열을 탐색하면서 해당 정수의 값을 tmp 배열의 인덱스에 +1 씩 업데이트한다.

업데이트한 배열을 재탐색하면서 값이 0인 경우는 missing value라고 판단, 2회 나온 값은 이중으로 나온 값으로 판단하고 해당 두 값을 리스트에 담아 반환한다.

Code

 class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        missingVal, dubleVal = 0, 0
        tmp = [0] * (len(nums)+1)

        for num in nums:
            tmp[num]+=1

        for i, v in enumerate(tmp):
            if v==0:
                missingVal = i
            if v==2:
                dubleVal = i

        return [dubleVal, missingVal]

Complexicity

시간 복잡도

주어진 배열 n 만큼 탐색하므로 시간복잡도는 O(n)이 소요된다.

공간 복잡도

tmp 배열에 1~n까지의 원소를 할당하므로 공간복잡도는 O(n)이다,

---