⭐️ LeetCode 알고리즘 풀이 (with Python)

# Merge Sorted Array

[Quetion]

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

[Example 1]

• Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
• Output: [1,2,2,3,5,6]
  Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
  The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

---

📌 접근법

아직 알고리즘에 익숙하지는 않아서 주먹구구식 구현을 목표로 접근했다.

처음에는 단순히 m, n 만큼 리스트 요소를 추출하고 내용을 합쳐서 정렬하는 문제인 줄 알아서 새로운 리스트를 정의하고 nums1과 nums2를 m, n 만큼 리스트 슬라이싱하여 담은 후 for문 2개를 돌려 정렬 했다.

하지만, 그것은 문제를 잘못봤던 것이고 문제에서는 nums1에 합치고 정렬하라는 뜻이었다.

그래서 다음과 같이 생각했다.

nums1에서 필요 없는 m요소 이후 만큼 지운다.
nums1에서 m까지 추출한 것에 nums2에서 n까지 추출한 것을 더한다.

for i 1부터 m+n까지 반복:
	for j m+n까지 반복:
    	if nums[i] < nums[j]이면
        	nums[i]와 nums[j]를 교체한다.

생각 그대로 코드로 구현 해보았다.

class Solution(object):
    def merge(self, nums1, m, nums2, n):
		# nums1에서 필요 없는 만큼 슬라이싱 하여 del()로 삭제
        del(nums1[m:])
        
        # nums2에서 n만큼 슬라이싱 하여 nums1에 더하기
        nums1[0:m] += nums2[0:n]
		
        # nums1[i]가 nums1[j] 보다 작으면 교체
        for i in range(1, m+n):
            for j in range(m+n):
                if nums1[i] < nums1[j]:
                    nums1[i], nums1[j] = nums1[j], nums1[i]
        
        return nums1

Runtime : 32ms
Memory : 13.4 MB

for문이 2번이나 돌아서 Runtime이 상대적으로 길어졌다는 것을 알 수 있었고, for문을 없애는 방법에 대해 고민해보았다.

---

📝 Merge Sorted Array 회고

문제를 해결하고 다른 사람들의 Solution을 참고 했는데 sort() 함수를 사용하면 안되는 줄 알았지만 sort()함수로 구현한 코드가 있었다.

또 다른 방법으로는 i, j 두개의 포인터를 만들어서 해결한 점은 비슷하지만 for문 2개를 활용하여 포인터를 생성하는게 아니라 변수에 할당하여 while문 하나로 작성한 코드였다.

참고한 코드들에 비해 확실히 내가 작성한 코드는 시간, 공간 복잡도 모두 높아보였다. 그래서 우선 for문을 제거하는 방법을 개선 1순위로 생각했기 때문에 sort()를 활용하여 다시 수정해보았다.

# 수정 후
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        del(nums1[m:])
        nums1[0:m] += nums2[0:n]
        
        # 정렬 부분을 sort() 함수로 수정 
        nums1.sort()

Runtime : 32ms ---> 22ms
Memory : 13.4 MB ---> 13.2 MB

정렬 부분을 sort()함수로 수정 후 확실하게 Runtime과 Memory 모두 줄어들었고, 결과적으로 Runtime은 10ms, Memory는 2MB 개선 효과가 나타났다.

그래서 sorted()도 시도해보았지만 sorted()는 리스트 원본을 유지하고 정렬 값을 반환하는 내장함수이기 때문에 테스트를 통과하지 못했다.

반면에 sort()는 리스트형의 메소드이며 원본값을 수정하기에 해당 문제에서 사용할 수 있다는 것을 알았다. 이번 문제와 같이 리스트 원본을 정렬하는 문제의 경우 sorted()와 sort()의 차이를 헷갈리지 않도록 유의해야겠다.

---

---

# Remove Element

[Quetion]

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.
Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
// It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.

[Example 1]

• Input: nums = [3,2,2,3], val = 3
• Output: 2, nums = [2,2,,]
  Explanation: Your function should return k = 2, with the first two elements of nums being 2.
  It does not matter what you leave beyond the returned k (hence they are underscores).

---

📌 접근법

처음에는 val과 리스트 속의 요소가 같으면 지우면 되겠다는 단순한 생각으로 접근했다. 하지만 리스트 개수대로 반복 하라는 for문으로 반복할 경우 리스트 속 요소를 지우게 되면 리스트의 인덱스가 범위를 벗어나게 된다.

이러한 문제를 해결하기 위해 while문으로 반복하여 리스트 속 요소와 val이 같은지 판단하기로 했고, i가 리스트의 수 보다 크거나 같을 경우 반복문을 탈출하도록 설계하여 list index out of range를 방지했다.

그리고 val에 해당하는 리스트 요소를 지우게 되면 리스트의 개수도 줄어들기 때문에 리스트의 인덱스를 지칭하는 i값 또한 감소시켜 줌으로써 리스트 범위를 벗어난다는 에러를 사전 방지했다.

class Solution(object):
    def removeElement(self, nums, val):
        i=0
        
        while True:
        	# 만약 i가 nums 길이보다 크거나 같으면 반복문 종료
            if i >= len(nums):
                break
            
            # nums[i]가 val과 같으면 해당 요소 지우고, i는 -1
            if nums[i] == val:
                del(nums[i])
                i -= 1
            
            # i 값 1씩 증가
            i+=1

        return len(nums)

Runtime : 15ms
Memory : 13.2 MB

Runtime은 상위 80%, Memory는 상위 55%로 비교적 빠른 Runtime을 가진 코드를 작성하게 되었다.

---

📝 Remove Element 회고

다른 사람들의 Solution을 확인해보니 코드로 구현하고자 하는 것은 내가 작성한 코드와 생각이 비슷했다는 것을 알 수 있었고, 다만 while문이 아닌 for문을 활용했고 nums[i]가 val과 같지 않는 경우의 조건을 부여하였다는 점이 차이점이었다.

그래서 변수를 더 할당해야하는 for문으로 수정하기 보다는 del()함수를 교체하는 방법으로 수정해보았다.

class Solution(object):
    def removeElement(self, nums, val):
        i=0
        while True:
            if i >= len(nums):
                break

            if nums[i] == val:
            	# del() 함수 대신 remove()함수 사용
                nums.remove(nums[i])
                i-=1
            
            i+=1

Runtime : 15ms ---> 11ms
Memory : 13.2 MB ---> 13 MB

함수만 교체했을 뿐이지만 Runtime 4ms, Memory 0.2MB의 개선효과가 있었다. 적은 수이지만 LeetCode기준 Runtime은 15%, Memory는 43%의 상승으로 유의미한 결과를 얻었다.

del()에 비해서 remove() 함수가 메모리와 속도 면에서 차이가 있다는 것을 알 수 있었고, 왜 그런 것인지 찾아보았다. del은 인덱스 기반으로 요소를 제거하고 시간복잡도는 O(1)을 가지며, remove는 값을 기준으로 요소를 제거하고 O(N)의 시간복잡도를 가진다.

그래서 인덱스를 알고 있을 경우 del이 더 빠를 수 있지만, 해당 문제에서는 입력되는 리스트의 양이 적어서 remove의 실행시간이 더 적었던 것 같다.

---

---

# Remove Duplicates from Sorted Array

[Quetion]

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
Return k.
Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.

[Example 1]

• Input: nums = [1,1,2]
• Output: 2, nums = [1,2,_]
  Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
  It does not matter what you leave beyond the returned k (hence they are underscores).

---

📌 접근법

리스트 내의 중복 요소를 삭제하는 것은 다른 말로 리스트 내의 특정 요소를 삭제하라는 것과 비슷하다고 생각했고, 이전 Remove Element 코드를 그대로 응용해봤다.

달라진 것은 nums[i-1]에 해당하는 값이 nums[i]와 같으면 nums[i]를 삭제하라는 것이다. nums[i]와 nums[i+1]로 비교할 시 마찬가지로 리스트 범위 밖의 값이라는 오류가 발생하기 때문에 i-1값과 i값을 비교했다.

class Solution(object):
    def removeDuplicates(self, nums):
        i = 1
        while True:
            if i >= len(nums):
                break

            if nums[i-1] == nums[i]:
                del(nums[i])
                i-=1
            
            i += 1
        
        return len(nums)

Runtime : 122ms
Memory : 14.1 MB

테스트 케이스의 범위가 큰데 while 문을 사용하여 Runtime이 상대적으로 길게 나왔다.

---

📝 Remove Element 회고

다른 사람들의 코드를 참고한 결과 sorted()함수와 set()함수를 활용한 코드, 포인터를 하나 더 추가한 for문 코드 등이 있었다.

set()함수는 알고 있었지만 새로운 변수에 할당해야 해서 사용하지 못했지만 nums[:]로 선언하면 리스트의 복사본이 아닌 원본 리스트와 동일한 객체에 접근 할 수 있기 때문에 set()과 sorted()를 활용할 수 있게 된다.

그래서 이를 참고하여 기존 코드를 수정해보았다.

class Solution(object):
    def removeDuplicates(self, nums):
    	# while문 제거, set()으로 중복 제거 후 sorted()로 정렬
        # 정렬된 값을 nums[:]로 nums를 전체 슬라이싱한 객체에 저장 
        nums[:] = sorted(set(nums))

Runtime : 122ms ---> 55ms
Memory : 14.1 MB ---> 14.3 MB

코드가 매우 간결 해지고 Runtime 67ms의 개선효과가 있었다. 하지만 간결해진 코드에 비해 Memory는 큰 차이가 없는 것을 알 수 있었다.

그래서 다른 방법으로도 시도를 해보았는데, 이전의 while문에서는 nums[i-1]과 nums[i]가 같으면 해당 요소를 삭제하는 방법을 사용했다.

이를 바꾸어서 nums[i-1]과 nums[i]이 다른 경우, 새로운 포인터 j를 두어 nums[j]와 nums[i]를 교체해주는 방법을 사용해보았다. 핵심은 문제에서 리스트 앞 요소 k만큼을 제외한 다른 값이 삭제 되거나 교체 되는 것을 신경쓰지 않는 다는 것을 활용하여 삭제 과정을 없앤 것이다.

class Solution(object):
    def removeDuplicates(self, nums):
        i = 1
        j = 1
        while True:
            if i >= len(nums):
                break
            if nums[i-1] != nums[i]:
   				# 삭제하는 del 대신 j포인터로 요소 교체
                nums[j] = nums[i]
                j+=1
            i+=1
        return j

Runtime : 122ms ---> 61ms
Memory : 14.1 MB ---> 14.2 MB

그 결과 처음보다는 Runtime 61ms의 개선효과와 Memory 0.1MB 증가를 확인할 수 있었고, 1차 수정 이후와 비교했을 경우 Runtime 6ms 증가 Memory 0.1MB 감소한 것을 확인할 수 있었다.

최종적으로 1차 수정 함수 코드와 2차 수정 while문 코드는 성능이 비슷하다는 것을 알 수 있었고, 함수를 아는 경우에는 python의 장점을 살린 1차 수정 코드가 더 괜찮다고 생각했다.

함수를 활용 할 수 없는 경우를 대비해서 2차 수정 코드와 같이 반복문과 !=의 반대 상황에 대해 익숙해지도록 더 노력해야겠다는 생각을 했다.