[LeetCode 2094] Finding 3-Digit Even Numbers

문제개요

문제:  https://leetcode.com/problems/finding-3-digit-even-numbers

 

정수 배열 digits가 주어졌을 때, 이 배열 내의 세 자릿수를 임의의 순서로 이어 붙여 만들 수 있는 중복 없는 짝수 세 자릿수를 모두 구해야 합니다. 조건은 다음과 같습니다.

• 각 숫자는 digits 배열에서 서로 다른 인덱스에서 선택된 세 개의 요소로 구성됩니다.
• 생성된 정수는 세 자리 수여야 하며, 0으로 시작해서는 안 됩니다.
• 마지막 자릿수는 짝수여야 하므로 2, 4, 6, 8, 0 중 하나여야 합니다.
• 결과는 정렬된 상태로 반환해야 합니다.

 

예시:

입력: [1, 2, 3]

출력: [132, 312] (예: 132는 1, 3, 2를 조합한 것이며, 짝수이고 0으로 시작하지 않음)

 

접근방식

• 데이터의 크기가 작기 때문에, 세 개의 서로 다른 인덱스를 선택해 세 자릿수를 만들기 위해 3중 반복문을 사용합니다.
• 첫 자리는 0이 될 수 없으므로 건너뜁니다.
• 마지막 자리는 짝수인지 확인하여 조건을 만족하는지 필터링합니다.
• 중복 제거를 위해 set 자료구조를 사용합니다.
• 최종적으로 정렬하여 반환합니다.

구현

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        n = len(digits)
        res=set()
        for i in range(n):
            if digits[i] == 0:
                continue
            for j in range(n):
                if i==j:
                    continue
                for k in range(n):
                    if digits[k] % 2 or j == k or k == i:
                        continue
                    res.add(digits[i] * 100 + digits[j] * 10 + digits[k])                
        return sorted(res)

 

 

시간 복잡도

• 최악의 경우 세 중첩 반복문으로 인해 O(n³) 시간 복잡도를 가집니다.
• 하지만 n의 최대 크기가 작다면(예: 100 이하), 실제 성능에는 큰 문제가 없습니다.

공간 복잡도

• set을 사용해 최대 900개의 세 자릿수(100~998 사이 짝수)를 저장할 수 있으며, 이는 O(1) 입니다.
• 결과를 정렬해 리스트로 변환하는 과정에서 추가적인 리스트 공간이 필요하지만, 숫자가 정해져 있므로 수로 O(1) 입니다.