⭐️ LeetCode 알고리즘 풀이 (with Python)
# Conatins Duplicate II
[Quetion]
📌 접근법
[문제 이해]
- 서로 다른 두 인덱스에 해당하는 값이 k보다 적거나 같은 만큼 떨어져 있으면 True 반환
처음 이해는 k만큼 떨어져 있으면 True를 반환한다고 생각했으나, 문제에서 abs(i-j) <= k 라는 요구조건이 있으므로 틀렸다는 것을 알 수 있다.
k만큼 떨어져 있다고 생각한다면 nums=[99, 99], k=2일 때 abs(0-1)=1 이므로 False가 반환 되지만 문제에서는 abs(i-j) <= k 이므로 1<= k 이기 때문에 True가 반환되어야 한다.
그래서 다음과 같은 생각의 흐름대로 구현 해보았다.
- nums에서 중복 요소를 삭제하고, 해당 요소가 key 값이 되는 dict 자료형을 만든다
- key 값에 맞는 인덱스들을 value에 리스트 형식으로 추가한다
- 만약 value를 2개 이상 가지고 있다면 value끼리 - 연산을 진행한 값이 k보다 작으면 True 반환
💻 구현
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
# key : value 형태의 dict 생성
hash_nums = {}
# 요구 리스트의 중복제거
set_nums = set(nums)
# 중복 제거한 값을 dict에 key로 추가
for j in set_nums:
hash_nums[j]=None
# key의 value가 비어있지 않으면 해당 요소의 인덱스 값 추가
for i, val in enumerate(nums):
if hash_nums.get(val) != None:
hash_nums[val].append(i)
# 비어있다면 인덱스를 리스트에 담아 dict에 저장
else:
hash_nums.update({val:[i]})
# value = 중복 제거 전의 리스트 요소
for n in hash_nums:
value = hash_nums.get(n)
# 리스트 요소의 인덱스 값이 2개 이상 저장되어 있는 경우
if len(value) >= 2:
for l in range(len(value)):
# 인덱스가 list 범위를 벗어나는 것을 방지
if l+1 == len(value):
break
# 인덱스 간의 격차가 k보다 작거나 같으면 True
if abs(value[l] - value[l+1]) <= k:
return True
return FalseRuntime: 650ms | Memory: 39.8MB
LeetCode 코드 중 Runtime 10%, Memory 6% 해당하는 결과
📝 Conatins Duplicate II 회고
-
리스트 요소 별 인덱스 간의 격차를 확인하는 과정에서 중복 for문을 사용하여 시간복잡도가 O(n^2)으로 높게 나왔다.
-
key 값에 해당하는 인덱스를 저장하는 과정에서 O(n)의 공간복잡도를 가졌고 전체적으로 개선이 필요하다.
-
중복 for문을 제거하고, 인덱스의 격차를 k와 비교하는 과정과 인덱스를 저장하는 과정을 합치면 시간, 공간복잡도 모두 개선할 수 있을 것 같다.
# 개선 후
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
hash_nums = {}
for i, val in enumerate(nums):
# 만약 dict에 리스트 요소(key)값이 있고,
# 두 인덱스 간의 격차가 k보다 작거나 같으면 True
if val in hash_nums and abs(i-hash_nums[val]) <= k:
return True
# key에 인덱스 업데이트
hash_nums[val] = i
return FalseRuntime: 650ms ---> 509ms
Memory: 39.8MB ---> 29.8MB
이전 코드와 의미상 비슷하지만 key에 인덱스를 모두 저장하는 과정을 업데이트 하는 방법으로 변경하고, k와 인덱스 간의 격차를 확인하는 조건을 합쳤다.
코드도 훨씬 간결해지고, 시간복잡도 역시 O(n)으로 감소하여 Runtime 141ms 만큼의 개선효과를 얻었다.
다른 사람들의 코드를 참고했을 때 수정 된 코드와 같은 방식으로 많이 접근 했고, 기존에 활용하던 enumerate()를 활용하여 솔루션에서 참고했던 코드들 보다 간소화 시켜보았다.
# Ransom Note
[Quetion]
📌 접근법
[문제 이해]
- magazine 문자열로 ransomNote를 만들 수 있으면 true 아니면 false
- 단, magazine 문자열은 중복 사용 불가
두 개의 dict를 생성하여 value 값을 비교하면 되겠다는 생각으로 다음과 같이 흐름을 구성했다.
- ransomNote의 중복값을 배제한 리스트의 값으로 key 생성
- ransomNote 값이 key로 담긴 딕셔너리의 value에 값들의 개수 저장
- magazine도 같은 방법으로 딕셔너리 생성
- ransomNote 키에 해당하는 value 보다 동일한 key를 가지고 있는 magazin의 value가 없거나 작으면 False
- 아니면 True
💻 구현
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
ran = set(ransomNote)
mag = set(magazine)
ran_dict = {}
mag_dict = {}
# ransomNote의 요소를 key로 잡고 해당 요소의 개수를 value에 저장
for i in ran:
ran_dict[i] = ransomNote.count(i)
for j in mag:
mag_dict[j] = magazine.count(j)
# magazine의 요소 개수가 ranomNote의 요소 개수와 비교시 없거나 적으면 False
for r in ran_dict:
if mag_dict.get(r) == None:
return False
if ran_dict.get(r) > mag_dict.get(r):
return False
return TrueRuntime: 42ms | Memory: 16.6MB
LeetCode 코드 중 Runtime 93%, Memory 10% 해당하는 결과
📝 Ransom Note 회고
- for문이 3개나 있어서 복잡해 보이지만 최악의 경우 O(n)의 시간복잡도와 O(n)의 공간복잡도를 가지고 있다.
- Runtime은 빠르지만 dictionary 자료형을 두개 생성하여 저장하는 과정이 2번 반복되므로 Memory 사용량은 낮게 나왔다.
- dict에 요소 별 개수를 저장하지 않고, 두 리스트의 요소 개수를 바로 비교할 수 있도록 함축하게 된다면 따로 저장과정이 없으니 O(1)의 공간복잡도로 개선할 수 있을 것이다.
# 개선 후
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
# 중복 제거한 ransomNote만큼 반복
for r in set(ransomNote):
# magazine에서 ransomNote의 요소 개수 보다 작으면 False
if magazine.count(r) < ransomNote.count(r):
return False
return TrueRuntime: 37ms ---> 41ms
Memory: 16.6MB ---> 16.4MB
magazine과 ransomNote의 요소 개수를 비교한다는 핵심은 같지만 개수를 저장하지 않고 바로 비교함으로써 코드도 간결해지고 Runtime, Memory 모두 개선되었다.
Memory가 0.2MB의 차이가 나지만 91%로서 이전과 비교했을 때 보다 80% 정도 가량 높게 나왔고, 공간복잡도 계산으로도 O(1)을 가지며 개선한 것을 확인할 수 있었다.
# Valid Anagram
[Quetion]
📌 접근법
[문제 이해]
- t 문자열을 정확히 한 번 사용해서 s 문자열을 만들 수 있으면 True
이전 383. RansomNote 문제와 굉장히 유사한 문제라고 판단하여 같은 접근 방법으로 구현해보았다.
💻 구현
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
set_s = set(s)
set_t = set(t)
s_dict = {}
t_dict = {}
for i in set_s:
s_dict[i] = s.count(i)
for j in set_t:
t_dict[j] = t.count(j)
# 두 dict 중 key 값이 더 많은 dict 반환
new_dict={}
if len(s_dict) > len(t_dict):
new_dict = s_dict
else:
new_dict = t_dict
for r in new_dict:
if s_dict.get(r) == None or t_dict.get(r) == None:
return False
if s_dict.get(r) > t_dict.get(r):
return False
return TrueRuntime: 37ms | Memory: 16.9MB
LeetCode 코드 중 Runtime 99%, Memory 36.9% 해당하는 결과
📝 Valid Anagram 회고
-
Ransom Note와의 차이점은 테스트 케이스에서 비교 기준으로 잡은 dict의 key 수가 s가 적거나 t가 적은 상황이 발생하기에 s, t 둘 중 key값이 더 많은 dict를 기준으로 비교하게 구성했다.
-
Runtime은 99%로 굉장히 높게 나왔고, Memory는 비교적 낮게 나와서 RansomNote에서 코드를 간소화 했던 것 처럼 개선을 해보았다.
# 개선 후
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# 두 문자열의 개수가 다르면 False
if len(s) != len(t):
return False
# 중복을 제거한 s 문자열의 개수가 t문자열과 같지 않으면 False
for i in set(s):
if s.count(i) != t.count(i):
return False
return TrueRuntime: 37ms ---> 40ms
Memory: 16.9MB ---> 16.8MB
"모든 문자열을 한 번 사용하여 다른 단어나 구문의 문자를 재배열하여 형성되는 단어나 구문"이 Anagram의 특성이기 때문에 문자열의 개수가 다르다면 무조건 False라는 뜻이다.
그래서 이 핵심을 활용하여 조건문을 구성하고 각 문자열의 요소 개수를 비교하는 과정도 간추리게 되었다.
결과적으로 성능상 큰 차이는 없지만 0.1MB의 Memory (60%) 사용량을 개선했고 코드가 간결해지면서 코드의 가독성 또한 높일 수 있었다.
별개로 솔루션을 보면서 놀라웠던 코드가 있었다. 각 문자열을 sorted()로 정렬한 뒤 같지 않으면 False를 반환하는 코드를 보았는데, 성능은 개선한 코드보다 떨어졌지만 Anagram 즉, 문제의 특성을 잘 활용한 코드 같아서 굉장히 참신했다.
이렇게도 접근할 수 있겠구나를 깨달을 수 있는 코드였고, 문제 이해도를 높여서 창의적으로 풀 수 있는 능력을 키워야겠다는 생각을 할 수 있었던 코드였다.
