⭐️ LeetCode 알고리즘 풀이 (with Python)
# Sort List
[Quetion]
📌 접근법
[문제 이해]
- 요구된 링크드 리스트를 오름차순으로 정렬
요구된 링크드 리스트 자체만 활용하여 정렬하라는 조건은 없었다.
그래서 링크드 리스트의 데이터를 다른 배열에 반환하고 정렬한 후, 다시 새로운 링크드 리스트에 담는 방법을 생각했다.
💻 구현
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 링크드 리스트의 데이터가 없거나 다음 값이 없으면 그대로 반환
if head is None or head.next is None:
return head
# 결과를 담을 링크드 리스트
dummy = head
current = dummy
# 데이터를 담을 리스트
sort_list = []
while head:
sort_list.append(head.val)
head = head.next
# 데이터를 오름차순 정렬
sort_list.sort()
for val in sort_list:
current.val = val
current = current.next
return dummyRuntime: 182ms | Memory: 38.6MB
LeetCode 코드 중 Runtime 99%, Memory 85% 해당하는 결과
📝 Sort List 회고
-
%를 기준으로 생각보다 결과 값이 더 좋게 나왔다.
-
다른 사람들의 코드도 확인해보니 접근 법이 완전히 달랐다. 대부분 퀵정렬과 병합정렬로 문제를 해결한 것 같다.
-
병합 정렬로 접근할 경우 코드는 상당히 복잡해지지만 O(nlogn)의 시간복잡도를 보장하므로 빠를 것이라 생각된다. 하지만 지금 작성한 코드도 빠른 성능을 가지고 있어서 추가적인 개선은 진행하지 않았다.
# Find Peek Element
[Quetion]
📌 접근법
[문제 이해]
- 정렬되지 않은 리스트 내에서 양 쪽의 값 보다 큰 Peek 값의 인덱스를 반환
- O(log n)의 시간복잡도
이해 한 그대로 구현한다면 i 값의 -1과 +1에 위치하는 값을 i값과 모두 비교 해야한다.
하지만 말을 조금만 바꾸어서 생각한다면, 리스트 내의 가장 큰 값은 양쪽에 위치한 값들 보다 무조건 크다고 생각했다.
그래서 리스트 내의 가장 큰 값을 찾고, 해당 값의 인덱스를 반환하면 되는 간단한 문제로도 해석할 수 있기 때문에 먼저 이 생각을 바탕으로 구현 해보았다.
💻 구현
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
"""
sorted 함수 = 병합정렬기반 O(nlogn) 보장
주변 값들 중 가장 큰 값의 인덱스 == 가장 큰 값의 인덱스
"""
sort_check = sorted(nums)
return nums.index(sort_check[-1])Runtime: 41ms | Memory: 16.4MB
LeetCode 코드 중 Runtime 98%, Memory 61% 해당하는 결과
📝 Find Peek Element 회고
-
Python에서 제공하는 Sorted() 함수의 시간복잡도는 O(nlogn)이다. 이 함수의 기반이 병합정렬이기 때문이다.
-
그래서 sorted()로 정렬하는 과정에서 O(nlogn)의 시간복잡도가 발생하는 것 이외에는 시간복잡도를 높이는 상황이 없기 때문에 제출이 통과된 것이다.
-
그렇지만 함수를 활용할 수 없는 상황에서 문제를 해결하기 위해서는 자료구조를 적극 활용 해봐야하므로 다른 사람들의 솔루션들을 참고하여 다시 구현해보았다.
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
# nums 길이가 1 이거나 0번째가 첫번째 보다 큰 경우 0
if len(nums) == 1 or nums[0] > nums[1]:
return 0
# 마지막 요소가 그 전 요소보다 크면 마지막 인덱스 값
elif nums[len(nums)-1] > nums[len(nums)-2]:
return len(nums) - 1
# 이진 검색
l,r= 0, len(nums)-1
while l <= r:
avg = (l+r) // 2
if nums[avg] > nums[avg+1] and nums[avg] > nums[avg-1]:
return avg
elif nums[avg] > nums[avg+1]:
r = avg - 1
else:
l = avg + 1Runtime: 41ms ---> 54ms
Memory: 16.4MB ---> 16.3MB
첫번 째 값과 마지막 값의 예외처리 이후 이진 검색 방법을 통해 접근했다.
리스트 내의 값이 하나밖에 없거나 두번 째 인덱스 값보다 크면 첫번째 인덱스 값을 반환하면 되기에 0을 반환한다.
마지막 값도 그 이전 값보다 크면 마지막 값이 Peek 요소이기 때문에 마지막 값의 인덱스를 반환한다.
이후 왼쪽과 오른쪽의 포인터를 생성하여 중간을 정하는 포인터를 생성하고 문제에서 이해한 대로 주변 값을 비교한 후 Peek 요소이면 중간을 가르키는 포인터를 그대로 반환했다.
성능상으로는 맨 처음 작성한 함수활용 코드와 비슷하지만, 함수를 사용할 수 없을 경우에는 이진 검색의 방법으로 접근하는 것이 가장 좋은 솔루션이라고 생각했고, 대부분 많이 조회한 솔루션도 이진검색이었다.
# Search in Rotated Sorted Array
[Quetion]
📌 접근법
[문제 이해]
- 배열 내의 요소들이 회전 할 수 있고, 회전한 배열에서 target값의 인덱스 반환
- target 값이 없으면 -1 반환
- O(log n)의 시간복잡도
가장 처음에는 target 값이 배열 내에 있으면 인덱스를 반환한다 라고 생각했다.
하지만 in 연산자는 O(n)의 시간복잡도를 가지므로 요구사항을 지킬 수 없다.
따라서 sorted() 함수로 정렬된 리스트를 만든 후, 이진 검색의 방법을 활용하여 target 값이 있는지 확인했다.
💻 구현
class Solution:
def search(self, nums: List[int], target: int) -> int:
sort_nums = sorted(nums)
l,r = 0,len(nums)-1
# 만약 요소가 1개 이고, 그 요소가 타겟 값이면 0반환
if r == 0 and nums[0] == target:
return 0
while l <= r:
avg = (l+r)//2
if sort_nums[avg] == target:
return nums.index(target)
if sort_nums[avg] < target:
l = avg + 1
else:
r = avg - 1
return -1Runtime: 49ms | Memory: 16.7MB
LeetCode 코드 중 Runtime 58%, Memory 69% 해당하는 결과
📝 Search in Rotated Sorted Array 회고
-
이진검색의 방법을 활용하기 위해서는 리스트가 정렬되어 있어야 한다.
-
그래서 O(nlogn)의 시간복잡도를 가진 sorted()함수로 정렬 후, target값을 찾는 이진검색을 할 수 있었다.
-
다른 솔루션을 찾아보니 정렬하지 않고도 이진검색을 실시하되 조건문을 더 복잡하게 가져가는 방법들이 대다수 였다.
-
같은 이진 검색의 방법으로 접근해서 성능은 비슷하겠지만, 코드 복잡도가 더 증가하기 때문에 더 이상의 개선은 필요 없다고 판단했다.
