•
문제 설명 : 세 개의 숫자를 사용하여 0으로 시작하지 않고 짝수인 고유한 세 자리 수를 모두 찾아 오름차순으로 정렬된 배열로 반환
•
풀이 방법
◦
Brute Force로 진행하는 경우, 배열의 모든 요소를 탐색하여 조건을 확인한다.
◦
개선된 방식으로는 문제 내 범위가 3자리 양수임을 확인하여, 100 ~ 999 숫자를 탐색하고 조건에 맞는 경우 반환한다.
•
시간복잡도 :
•
성공 코드
class Solution:
def findEvenNumbers(self, digits: List[int]) -> List[int]:
result = set()
for i in range(len(digits)):
for j in range(len(digits)):
for k in range(len(digits)):
if i != j and j != k and i != k:
if digits[i] > 0 and digits[k] % 2 == 0:
result.add(100 * digits[i] + 10 * digits[j] + digits[k])
return sorted(result)
Python
복사
•
개선 코드(O(N))
Brute Force 방식은 시간복잡도가 너무 크기 때문에, 솔루션을 참고하였다.
일부 문제를 보니, 문제에서 세자리 수 한정임을 이용하여 100 ~ 999 숫자를 직접 사용하는 방식을 택하였다.
이 부분을 보고, 코드를 고쳐보았다.
from collections import Counter, defaultdict
class Solution:
def findEvenNumbers(self, digits: List[int]) -> List[int]:
result = []
info = Counter(digits)
for num in range(100, 1000, 2):
is_pass = False
temp = defaultdict(int)
# 현재 탐색중인 숫자의 사용중인 숫자 확인
for ch in str(num):
temp[int(ch)] += 1
# 제공된 배열 내 숫자 한도에서 해당 숫자를 만들 수 있는지 확인
for k, v in temp.items():
if info.get(k, 0) < v:
is_pass = True
break
if not is_pass:
result.append(num)
return result
Python
복사