문제 이해하기
배열 nums와 값 k가 주어졌을 때, 아래 연산을 정확히 k번 수행하여 배열의 모든 원소를 0으로 만들 수 있는지 확인하는 문제입니다.
연산의 정의
배열에서 가장 작은 원소를 선택한 뒤, 0이 아닌 나머지 모든 원소에서 그 값을 뺍니다.
동작 예시
입력이 nums = [2, 2, 3, 5], k = 3인 경우를 살펴보겠습니다. 결과는 True입니다.
1. 첫 번째 연산: 가장 작은 값 2를 빼면 배열은 [0, 0, 1, 3]이 됩니다.
2. 두 번째 연산: 0이 아닌 값 중 가장 작은 값 1을 빼면 [0, 0, 0, 2]가 됩니다.
3. 세 번째 연산: 다시 2를 빼면 [0, 0, 0, 0]이 되어 모든 원소가 0이 됩니다.
해결 접근 방법
이 문제의 핵심은 각 연산이 현재 남아 있는 값들 중 가장 작은 값을 한꺼번에 없앤다는 점입니다. 즉, 연산 한 번당 하나의 '값 수준'이 사라지므로, 필요한 총 연산 횟수는 배열에 존재하는 서로 다른 값(고유 원소)의 개수와 같습니다.
따라서 해결 절차는 다음과 같습니다.
- 배열의 고유 원소 개수가 정확히 k개라면 True를 반환합니다.
- 그렇지 않다면 False를 반환합니다.
구현 코드
def solve(nums, k):
distinct = set(nums)
if len(distinct) == k:
return True
return False
nums = [2, 2, 3, 4]
k = 3
print(solve(nums, k))
입력
[2, 2, 3, 4], 3
출력
True
코드 설명
set(nums)를 사용하면 배열에서 중복을 제거한 고유 값들의 집합을 얻을 수 있습니다. 위 예제에서 [2, 2, 3, 4]의 고유 값은 {2, 3, 4}로 3개이며, k가 3이므로 함수는 True를 반환합니다. 이 방식의 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로 매우 효율적입니다.