문제
You are given an integer array digits, where each element is a digit. The array may contain duplicates.
You need to find all the unique integers that follow the given requirements:
- The integer consists of the concatenation of three elements from digits in any arbitrary order.
- The integer does not have leading zeros.
- The integer is even.
For example, if the given digits were [1, 2, 3], integers 132 and 312 follow the requirements.
Return a sorted array of the unique integers.
문제(번역)
정수 배열 digits가 주어집니다. 이 배열에는 중복된 숫자가 포함될 수 있습니다.
다음 조건을 만족하는 고유한 정수들을 모두 찾아야 합니다:
- 정수는 digits 배열에서 세 개의 요소를 임의의 순서로 이어 붙여서 만들어야 합니다.
- 정수는 0으로 시작하면 안 됩니다 (즉, 앞자리에 0이 오면 안 됨).
- 정수는 짝수여야 합니다 (즉, 마지막 자릿수가 짝수여야 함).
예를 들어, 주어진 digits가 [1, 2, 3]이라면 132와 312는 조건을 만족하는 정수입니다.
조건을 만족하는 고유 정수들을 오름차순 정렬된 배열로 반환하세요.
예시
Example 1:
Input: digits = [2,1,3,0]
Output: [102,120,130,132,210,230,302,310,312,320]
Explanation: All the possible integers that follow the requirements are in the output array.
Notice that there are no odd integers or integers with leading zeros.
Example 2:
Input: digits = [2,2,8,8,2]
Output: [222,228,282,288,822,828,882]
Explanation: The same digit can be used as many times as it appears in digits.
In this example, the digit 8 is used twice each time in 288, 828, and 882.
Example 3:
Input: digits = [3,7,5]
Output: []
Explanation: No even integers can be formed using the given digits.
예시(번역)
예시 1:
입력: digits = [2,1,3,0]
출력: [102,120,130,132,210,230,302,310,312,320]
설명: 조건을 만족하는 모든 가능한 정수들이 출력 배열에 포함되어 있습니다.
0으로 시작하는 수나 홀수는 포함되지 않습니다.
예시 2:
입력: digits = [2,2,8,8,2]
출력: [222,228,282,288,822,828,882]
설명: 같은 숫자는 해당 배열에 존재하는 횟수만큼 사용할 수 있습니다.
예를 들어, 8이 두 번 사용된 288, 828, 882가 가능합니다.
예시 3:
입력: digits = [3,7,5]
출력: []
설명: 주어진 숫자들로는 짝수인 세 자리 수를 만들 수 없기 때문에 빈 배열이 반환됩니다.
class Solution:
def findEvenNumbers(self, digits: List[int]) -> List[int]:
result = []
digits_len = len(digits)
for i in range(digits_len):
for j in range(digits_len):
if i == j:
continue
for k in range(digits_len):
if i == k or j == k:
continue
first_digit = digits[i]
second_digit = digits[j]
third_digits = digits[k]
if first_digit == 0:
continue
if third_digits % 2 != 0:
continue
number = first_digit * 100 + second_digit * 10 + third_digits * 1
if number not in result:
result.append(number)
return sorted(result)처음에는 위와 같이 코드를 작성했다.
-
기존에 주어지는 리스트를 순회하여 100의 자리 숫자를 찾은 후에 그 안에서 다시 모든 리스트를 순회하여 10의 자리를 숫자를 찾는다. 이 때, 처음에 찾은 100의 자리 숫자(i)와 두번째로 찾은 10의 자리 숫자(j)가 같다면 건너뛴다.
-
그리고 마지막으로 1의 자리 숫자를 찾은 후에 그 숫자를 100의 자리의 숫자(i)와 10의 자리 숫자(j)의 인덱스와 비교한 후에 일치하지 않다면 이어서 코드를 진행한다.
-
문제의 조건인 첫번째 자리가 0이면 건너띄고 마지막 숫자(1의 자리)가 짝수가 아니면 건너띈다.
-
최종 적으로 first_digit과 second_digit, third_digit에 저장된 숫자를 문자열 형식이 아닌 정수형태로 바꾸어주고 그 숫자를 number에 저장한 후에 처음에 만들어 놓은 result라는 배열에 그 숫자가 없으면 그 숫자를 result 리스트에 넣어주어 마무리를 한 후, result를 정렬하여 출력한다.
이런 방식으로 코드를 작성하였고 test case는 통과를 하여 제출을 했는데 time limit이 발생하였다.
그래서 다시 나온 코드가 아래 코드이다.
class Solution:
def findEvenNumbers(self, digits: List[int]) -> List[int]:
result = set()
digits_len = len(digits)
for i in range(digits_len):
for j in range(digits_len):
if i == j:
continue
for k in range(digits_len):
if i == k or j == k:
continue
first_digit = digits[i]
second_digit = digits[j]
third_digits = digits[k]
if first_digit == 0:
continue
if third_digits % 2 != 0:
continue
number = first_digit * 100 + second_digit * 10 + third_digits * 1
if number not in result:
result.add(number)
return sorted(result)크게 달라진 것은 없다. 단지 result를 빈 리스트로 만들어주는 것이 아니고 set()을 사용하여 빈 집합을 만들어 주는 방식이다.
기존의 코드는 number not in resul가 리스트 전체를 처음부터 끝까지 비교해서 찾는 방식인데 반해 set()을 사용하면 해시 테이블을 사용하여 거의 즉시 값을 찾아낼 수 있기에 매우 빠르다고 한다.
