오늘은 어렵지 않습니다만, 삽질할 가능성이 있는 문제에 대해 다뤄보겠습니다.
이 문제는 알고리즘 복잡도와 효율적인 자료구조 사용에 대한 이해를 시험하는 좋은 연습이 될 것입니다.
해당 문제에서는 주어진 배열 nums 를 비우기 위해 필요한 최소 작업 횟수를 찾는 것입니다.
각 작업에서 nums 내의 똑같은 숫자를 제거할 수 있는데, (2개를 삭제하든지 3개를 삭제하든지) 둘 중 하나의 operation(연산)을 수행하면 서 nums 의 원소들을 제거하는 원리입니다.
최종적으로 nums 가 비워질 때까지 연산을 계속해서 하되, 최소의 연산으로 nums 를 비워야 하고, 이 때 이 최소의 연산 횟수를 반환하는 문제입니다.
제가 처음 접근한 방식은 각 숫자의 빈도수를 계산하여 동적 프로그래밍(DP)를 사용하는 것이었습니다. 하지만, 이 방법은 시간초과가 발생했습니다.(Time Limited Exceeded,TLE) DP 로 끝나는 것이 아니라, 추가적으로 또 count 하면서 DP 배열을 활용했어야 했기 때문에, 추가적인 복잡도가 늘어난 것 같습니다.
초기 코드는 아래와 같습니다.
# TLE solution
class Solution(object):
def minOperations(self, nums):
answer = 0
# 사용 가능한 명령(작업)의 경우의 수 - 2개 삭제 or 3개 삭제
command_case = [2,3]
# 중복을 제거한 숫자들의 집합 생성
nums_set = list(set(nums))
# 배열 내 가장 많이 등장하는 숫자의 등장 횟수를 찾기 위한 변수
max_cnt = 0
for i in nums_set:
max_cnt = max(max_cnt,nums.count(i))
# 무한대를 나타내는 값으로 초기화
max_val = float('inf')
# dp 를 위한 배열 초기화
# 각 인덱스는 숫자가 등장하는 횟수를 나타내며,
# 각 값은 해당 횟수를 달성하기 위한 최소 작업 횟수를 나타냄.
dp = [max_val] * (max_cnt+1)
dp[0] = 0
# 동적 프로그래밍을 통해 각 등장횟수에 대한 최소 작업 횟수를 계산.
for i in range(2):
for j in range(command_case[i],max_cnt+1):
dp[j] = min(dp[j],dp[j-command_case[i]] + 1)
# 각 숫자에 대해 필요한 최소 작업 횟수를 계산하여 답에 더함
for n in nums_set:
cnt = nums.count(n)
# 만약 특정 숫자를 제거하는 데 필요한 작업 횟수가 계산되지 않았다면, -1을 반환
if dp[cnt] == max_val:
return -1
else:
# 계산된 작업 횟수를 답에 더함
answer += dp[cnt]
return answer
위 코드는 최소 동전교환(DP, 냅색 알고리즘) 문제에서 쓰이는 알고리즘을 사용했습니다.
동전문제에 비교해서 이 문제를 적용한다면, 나에게 지금 2원,3원 짜리 동전이 무한대로 있고, 이걸로 x 원을 만드는 데 최소 개수를 찾는 알고리즘입니다.
예를 들어, 8원을 만든다고 하면, (2원짜리 1개와 3원짜리 2개) 로 총 3개의 동전으로 8원을 만들 수 있는 셈입니다.
그 역할을 하는 부분이 dp를 사용한 이 중 for 문입니다.
하지만, 여기서 원하는 답까지 도출하려면, nums 배열에 있는 '가격'을 만들 수 있는 최소개수의 합을 구해야 하므로,
중복된 가격이 제외된 각 가격만 적혀져 있는 nums_set 을 순회하면서 각 '가격'이 최소 몇개의 동전을 필요로 하는지, answer에 더한 값이 답이 되는 것입니다.
위 코드는 시간복잡도가 딱봐도 복잡해보입니다. 우선 제한사항을 보면, nums 의 길이는 10^5까지입니다.
N 이 nums배열의 길이이고, M 이 nums_set 의 크기라면,
위 코드를 종합하면 시간복잡도는
1. O(N) (중복 제거 및 nums_set 생성)
2. O(N*M) (최대 빈도수 max_cnt 계산 )
3. O(max_cnt) (dp 배열 초기화)
4. O(max_cnt) (dp를 사용한 최소 작업 횟수 계산)
5. O(N*M) (최종 결과 계산) 로,
O(N) + O(N*M) + O(max_cnt) + O(max_cnt) + O(N*M) = O(N*M) 이라고 할 수 있습니다.
즉, N(10^5) 이 크고 nums 배열 내의 고유한 숫자가 많을 경우(최대 10^5), 이코드는 10^10 로 매우 비효율적인 코드가 됩니다.
DP 배열을 다시 분석해봤습니다.
사실 맨 처음 문제를 풀다가도 분명 규칙이 있을거라고 느꼈지만, 15까지만 하고 그 이후에는 dp 로 풀면 되겠다고 생각했습니다.
하지만, 계속해서 규칙을 찾다보면, 아래와 같은 규칙을 발견할 수 있었습니다.
# 1 -> 0
# 2 -> 1
# 3 -> 1
------
# 4 -> 2
# 5 -> 2
# 6 -> 2
------
# 7 -> 3
# 8 -> 3
# 9 -> 3
------
# 10 -> 4
# 11 -> 4
# 12 -> 4
------
# 13 -> 5
# 14 -> 5
# 15 -> 5
------
# 16 -> 6
# 17 -> 6
# 18 -> 6
------
# 19 -> 7
# 20 -> 7
# 21 -> 7
------
# 22 -> 8
# ...
결국, 4부터는 3번씩 증가값이 계속적으로 반복되는 것을 알 수 있습니다. 규칙성 있는 증가추이라서 dp를 굳이 생각해서 배열을 만들지 않아도 되는 것이였죠.
이처럼, 숫자의 빈도수에 따라 필요한 작업 횟수가 일정한 패턴을 보였는데, 이를 잘 보면 3의 배수를 기준으로 값이 바뀌는 것을 알 수 있습니다.
개선된 최종 코드를 작성해보면 아래와 같습니다.
class Solution(object):
def minOperations(self, nums):
# 배열 길이가 2인 경우의 특별 처리
if len(nums) == 2:
# 두 요소가 다르면 -1 반환 (불가능한 경우)
if nums[0] != nums[1]:
return -1
# 두 요소가 같으면 1 반환 (한 번의 작업으로 가능)
else:
return 1
# 각 숫자의 빈도수를 저장할 딕셔너리
counts = {}
for num in nums:
# 딕셔너리를 사용하여 각 숫자의 빈도수 계산
counts[num] = counts.get(num, 0) + 1
# 최종 답을 저장할 변수
answer = 0
for count in counts.values():
# 빈도수가 1인 경우 -1 반환 (불가능한 경우)
if count == 1:
return -1
# 빈도수가 3의 배수인 경우, 빈도수를 3으로 나눈 값만큼 작업 횟수 추가
if count % 3 == 0:
answer += (count // 3)
# 그렇지 않은 경우, 빈도수를 3으로 나눈 후 1을 더하여 작업 횟수 추가
else:
answer += (count // 3) + 1
return answer
이 코드의 로직은 이렇습니다.
- 배열 내 각 숫자의 빈도수를 계산하고, 이를 기반으로 최소 작업 횟수를 계산합니다.
- 문제에서 nums의 최소 배열은 2 라고 했으니까 배열 길이가 2인 경우는 예외 처리를 해줍니다. 두 요소가 같으면 한 번의 작업(2개 삭제)으로 가능하고, 다르면 불가능하므로 -1을 리턴합니다.(이 부분은 없어도 동작합니다. 어차피 counts에 담길 것만 담깁니다.)
- 각 숫자의 빈도수를 계산한 후, 빈도수가 1인 경우는 불가능한 경우로 처리합니다.(이 부분은 없어도 동작합니다. 어차피 counts에 담길 것만 담깁니다.)
- 빈도수가 3의 배수인 경우와 그렇지 않은 경우를 나누어 처리합니다. 3의 배수인 경우는 빈도수를 3으로 나눈 값이 작업 횟수가 되고, 그렇지 않은 경우는 빈도수를 3으로 나눈 후 1을 더한 값이 작업 횟수가 됩니다.
# 각 숫자의 빈도수를 저장할 딕셔너리
counts = {}
for num in nums:
# 딕셔너리를 사용하여 각 숫자의 빈도수 계산
counts[num] = counts.get(num, 0) + 1
특히, 이 부분은 Python 의 딕셔너리를 사용하여 배열 내 숫자의 빈도수를 계산하는 방법을 보여줍니다.
※ 문법적으로 짚고 넘어가야 할 점 → counts[num] = counts.get(num,0) + 1 분석
counts[num] = counts.get(num, 0) + 1 이 코드는 파이썬에서 특정 숫자의 빈도를 계산하는 데 사용됩니다.
여기서 counts는 딕셔너리이고, num은 카운트하고자 하는 특정 숫자입니다.
counts.get(num, 0): 이 부분은 counts 딕셔너리에서 num 키의 값을 가져옵니다. 만약 num 키가 딕셔너리에 없다면, 기본값으로 0을 반환합니다. 즉, num이 딕셔너리에 이미 있으면 그 값을, 없으면 0을 가져옵니다.
+ 1: counts.get(num, 0)의 결과에 1을 더합니다. 이는 num의 빈도를 하나 증가시키는 것을 의미합니다.
count[num] = ...: 마지막으로, num 키에 대한 값을 업데이트하여 새로운 빈도 수를 딕셔너리에 저장합니다. 결과적으로, 이 코드는 num이라는 키의 빈도 수를 counts 딕셔너리에 저장하고, num이 나타날 때마다 그 빈도 수를 하나씩 증가시킵니다. 이 방법은 리스트나 다른 시퀀스에서 각 요소의 빈도를 계산할 때 매우 유용합니다.
→ 다른 방법으로 이 부분을 작성해도 괜찮다. 예를 들어 Counter 클래스를 사용해서 작업을 더 간결하게 할 수도 있다.
from collections import Counter
counts = Counter(nums)
위 코드는 'nums' 배열의 각 요소의 빈도수를 자동으로 계산하고, 결과를 'counts' 딕셔너리에 저장합니다.
'Counter' 를 사용하면 'for'루프를 사용하여 수동으로 빈도수를 계산하는 대신, 한 줄의 코드로 동일한 결과를 얻습니다.
→ Counter 말고도 defaultdict 를 사용할 수도 있다.
from collections import defaultdict
counts = defaultdict(int)
for num in nums:
counts[num] += 1
'int' 함수를 기본값 팩토리로 사용하되, 'int'는 함수는 호출 될 때, 0을 반환하므로 새로운 키가 counts에 추가될 때 자동으로 0으로 초기화가 됩니다. 그런 다음, 각 숫자의 빈도수를 1씩 증가시킵니다.
그럼, 돌아와서 이제 시간복잡도를 분석해봅시다.
1. O(1) → (배열 길이 확인)
2. O(N) → (빈도수 계산)
- for num in nums : 루프는 'O(N)' 시간 복잡도를 가지고, 여기서 N 은 'nums' 배열의 길이입니다.
- counts.get(num,0) 는 평균적으로 'O(1)' 의 시간복잡도를 가집니다.
- 따라서, 빈도수 계산의 총 시간 복잡도는 'O(N)' 입니다.
3. O(M) → (최종 답 계산)
- for count in counts.values() : 루프는 'O(M)' 시간복잡도를 가집니다. 여기서 'M' 은 고유한 숫자의 개수입니다.
- 이 루프 내의 연산들은 모두 'O(1)' 시간복잡도를 가집니다.
- 따라서, 최종 답 계산의 총 시간 복잡도는 'O(M)' 입니다.
종합하면, 전체 코드 시간복잡도는 O(N + M) (최종 결과 계산) 입니다. 일반적인 경우 'N'이 'M'보다 크거나 같으므로, 전체 시간 복잡도는 주로 'O(N)' 에 의해 결정됩니다.
즉, 두번째 코드가 시간초과가 났던 코드보다 훨씬 효율적인 접근 방식입니다.
항상 문제를 풀 때는 시간복잡도를 고려하고 문제를 풀어야 합니다.
추가적으로, Counter 와 defaultdict(int) 와 dict.get(x,0) 은 동일한 작업을 하는 것도 배울 수 있는 문제였습니다!
이상으로 Counter 와 관련한 2870. Minimum Number of Operations to Make Array Empty 문제를 정리해봤습니다.
연관된 문제로 2244. Minimum Rounds to Complete All Tasks
Minimum Rounds to Complete All Tasks - LeetCode
Can you solve this real interview question? Minimum Rounds to Complete All Tasks - You are given a 0-indexed integer array tasks, where tasks[i] represents the difficulty level of a task. In each round, you can complete either 2 or 3 tasks of the same diff
leetcode.com
가 있으니, 풀어보시길 바랍니다. 해당 문제는 완전히 동일한 문제입니다.
'컴퓨터 공부 > 📚 Leetcode' 카테고리의 다른 글
| [리트코드/leetcode/python] 380. Insert Delete GetRandom O(1) (0) | 2024.01.16 |
|---|---|
| [리트코드/leetcode/python] 1235. Maximum Profit in Job Scheduling (2) | 2024.01.06 |
| [리트코드/leetcode/python] 1266. Minimum Time Visiting All Points (2) | 2023.12.03 |
| [리트코드/leetcode/python] 1685. Sum of Absolute Differences in a Sorted Array (0) | 2023.11.28 |
| [리트코드/leetcode/python] 1814. Count Nice Pairs in an Array (2) | 2023.11.21 |