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

# Remove Duplicates from Sorted Array II

[Quetion]

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

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,1,2,2,3]
• Output: 5, nums = [1,1,2,2,3,_]
  Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
  It does not matter what you leave beyond the returned k (hence they are underscores).

---

📌 접근법

이전 문제와 익숙하지만 차이점은 O(1)의 제한과 중복되는 요소를 두개로 남겨두는 점이다.

그래서 while문으로 접근했던 방식을 for문으로 바꾸어서 접근해야겠다는 생각과 for문 내부의 i를 변경할 수는 없기에 j라는 변수를 할당하여 리스트 내부의 요소를 탐색해야겠다는 생각으로 접근했다.

핵심은 j가 2일 때, nums[j] == nums[j-1] == nums[j-2]가 같으면 중복되는 요소 nums[j-2]를 제거하고 반복문에서 리스트 개수를 기준으로 반복하기 때문에 요소 삭제시 발생하는 리스트 범위를 벗어나는 것을 방지하고자 k 값을 요소를 삭제한 만큼 감소시켜줬다.

또한 선택한 요소가 삭제되었으므로 j값 또한 삭제한 만큼 감소시켜 리스트 내 요소를 정확히 지정할 수 있도록 해주었다.

리스트 개수를 변수에 할당
j=2
for i in range(2부터 리스트 개수까지 반복):
	만약 nums[j] == nums[j-1] == nums[j-2]이면 
    	nums[j-2]를 삭제하고 리스트 개수와 j값도 감소

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

class Solution(object):
    def removeDuplicates(self, nums):
    	# nums 리스트의 개수
        k=len(nums)
        
        j=2
        for i in range(2, k):
            if nums[j] == nums[j-1] == nums[j-2]:
                del(nums[j-2])
                k=k-1
                j-=1
            j+=1
                
        return len(nums)

Runtime : 26ms
Memory : 13.40 MB
Runtime은 상위 97% 정도로 빨랐지만 메모리는 38%로 비교적 많이 사용했다는 것을 알 수 있었다.

---

📝 Remove Duplicates from Sorted Array II 회고

다른 사람들의 코드들을 참고했을 때 현재 내가 구현한 코드와 의미상 비슷했다. 리스트의 개수를 변수에 할당할 필요가 없었고 if문도 조금 더 간결하게 표현할 수 있었다. 그리고 이전 문제와 마찬가지로 삭제가 아닌 교체의 방법으로 해결한 방법들이 많았다.

그래서 삭제가 아닌 교체의 방법으로 하면 어떤 효율로 나올지 궁금해서 코드를 수정해보았다.

class Solution(object):
    def removeDuplicates(self, nums):
        j=2
        for i in range(2, len(nums)):
        	# 만약 nums[i]와 nums[j-2]가 같지 않으면 [j]를 [i]값으로 교체
            if nums[i] != nums[j-2]:
                nums[j] = nums[i]
                j+=1    
        return j

Runtime : 26ms ---> 36ms
Memory : 13.40 MB ---> 13 MB

Runtime은 10ms 증가했고, Memory는 0.4MB 감소한 효과를 볼 수 있었다. 사실상 계속 같은 방법으로 실행 했을 경우 두 코드는 비슷한 성능이다. 그래서 !=의 방법이 아닌 nums[i]와 nums[j-2]가 같은 경우 continue를 활용하여 for문을 다음으로 넘기는 것을 활용하여 수정해보았다.

class Solution(object):
    def removeDuplicates(self, nums):
        j=2
        for i in range(2, len(nums)):
        	# 조건에 해당하면 pass
            if nums[i] == nums[j-2]:
                continue    
            nums[j] = nums[i]
            j+=1    
        return j

Runtime : 26ms ---> 27ms
Memory : 13.40 MB ---> 13.3 MB

조금의 차이지만 1차 수정된 코드보다 Runtime은 10ms 빠르게 나왔고 Memory도 0.1MB 정도 적게 사용할 수 있었다. 수정된 코드들 모두 기존의 코드에 비해서는 미세한 성능 향상이 있다고 생각하고, 무엇보다 읽고 이해하기는 더 쉬운 코드라고 생각했다.

알고리즘을 구현하는데에 있어서 성능도 좋지만, 비슷한 성능이라면 읽고 이해하기 쉬운 코드가 더 좋은 코드라고 생각하기 때문에 테스트가 아닌 실제 알고리즘 개발에 있어서 이러한 점도 유의하며 코드를 작성해야겠다고 생각했다.

---

---

# Majority Element

[Quetion]

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

[Example 1]

• Input: nums = [3,2,3]
• Output: 3

Follow-up: Could you solve the problem in linear time and in O(1) space?

---

📌 접근법

O(1)을 지키기 위해서는 for문을 여러 개 사용하면 안되겠다는 판단을 했다.

핵심은 가장 많은 중복 값을 가지는 수를 반환하면 되는 문제이기 때문에 각 요소 별로 몇 번 중복이 되는지 확인하고, 가장 많이 중복되는 수를 인덱싱하기로 생각했다.

다만 처음 nums의 요소를 전부 반복문을 통해 확인했더니 runtime이 초과되는 것을 확인했고, nums의 중복값을 모두 없애고 중복되지 않는 nums 값으로 반복문의 범위를 지정했다.

중복되는 값을 담을 리스트 선언
nums의 중복 값을 제거

for i in 중복 제거한 nums까지 반복:
	중복 개수를 리스트에 저장
    
중복 제거 리스트[중복 개수 리스트.index(최대 중복 값)]

이를 python 코드로 구현했을 때 다음과 같이 작성했다.

class Solution(object):
    def majorityElement(self, nums):
        count=[]
        num=set(nums)
        for i in num:
            count.append(nums.count(i))
        
        result=list(num)
        return result[count.index(max(count))]

Runtime : 124ms
Memory : 14.9 MB
Runtime이 124ms 이지만 LeetCode 기준 상위 75%의 시간 복잡도를 가진 코드로 비교적 빨랐고, 변수 할당을 많이 한 탓에 메모리가 14.9mb로 상위 47% 해당하여 비교적 많이 사용되었다는 것을 알 수 있었다.

---

📝 Majority Element 회고

이번 코드에서는 append, max, index 등 여러 함수를 사용했는데 비슷한 코드들도 있었으나 다른 코드들을 참고해보니 단순 for문 만으로 구현을 한 경우도 많았다.

또한 중복을 제거하지 않고 nums의 개수대로 for문을 활용한 코드가 많았는데, for문 안에서의 연산을 최대한 간소하게 줄인 것이 내 코드와의 차이점인 것 같다.

이를 참고하여 여러 함수를 사용하지 않는 방향으로 코드를 수정해보았다.

class Solution(object):
    def majorityElement(self, nums):
        major=0
        cnt=0
        N=list(set(nums))
        
        for i in range(len(N)):
        	# cnt에 nums 요소의 개수를 저장하고
            # 만약 cnt 보다 다른 요소의 개수가 클 경우 major에 해당 요소 저장
            if nums.count(N[i]) > cnt:
                cnt=nums.count(N[i])
                major=N[i]
                
        return major

Runtime : 124ms ---> 106ms
Memory : 14.9 MB ---> 14.9 MB

여러 함수를 사용했을 때 보다 Memory 사용은 비슷하지만 Runtime은 18ms 정도 개선할 수 있었다.

리스트 요소를 count()한 것을 append()로 추가하는 과정 보다 조건에 맞는 경우 변수에 초기화 해주는 것이 더 빠를 수 있다는 것을 알 수 있었다.

결론적으로 함수를 사용해서 코드를 간결하게 나타내는 것도 좋지만, 함수를 많이 사용한다해서 효율적인 것은 아니라는 것을 코드를 수정하며 검증했다.

---

---

# Rotate Array

[Quetion]

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

[Example 1]

• Input: nums = [1,2,3,4,5,6,7], k = 3
• Output: [5,6,7,1,2,3,4]
  Explanation:
  rotate 1 steps to the right: [7,1,2,3,4,5,6]
  rotate 2 steps to the right: [6,7,1,2,3,4,5]
  rotate 3 steps to the right: [5,6,7,1,2,3,4]

Follow-up

• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

---

📌 접근법

처음에는 python에서 마지막 요소를 삭제하고 반환하는 pop()함수와 값을 추가하는 insert()를 활용해서 k번 만큼 반복하면 되지 않을까? 하는 생각에 실행해보았지만 Time Over가 발생했다.

그래서 pop함수가 시간을 더 소비하는 건가? 싶어서 직접 마지막 요소를 슬라이싱하고 추가하는 과정을 넣고, for문의 반복 횟수를 줄여보고자 k로 리스트를 나눈 나머지 만큼만 반복하도록 구성하여 시도 했으나 여전히 TimeOver 상황이었다.

결론적으로 for문 같은 반복문은 사용하지 않고 풀어야 한다고 판단을 내렸고, 리스트 슬라이싱과 + 연산만을 사용해야겠다고 생각했다. 또한 리스트의 길이를 len(nums)으로 줄 경우 리스트 슬라이싱과 연산 과정에서 값이 유동적이므로 변수에 할당하여 고정했다.

# 첫 시도 -- Time Limit Exceeded
for i in range(k):
	nums.insert(0, nums.pop())
    
# 두번 째 시도 -- Time Limit Exceeded
if k==0:
	return nums

for i in range(k%len(nums)):
	# nums 마지막 요소 저장
	pop = nums[-1]
	# 마지막 요소 삭제
	del nums[-1]
	# 첫번째에 추가 
	nums.insert(0, pop)

이후 정말 많은 테스트 케이스와 수정을 거치면서 완성된 코드는 다음과 같다.

class Solution(object):
    def rotate(self, nums, k):
    	# 리스트 길이 저장
        count = len(nums)

		# 만약 k가 0 이거나 리스트 길이가 1보다 작거나 같으면 그대로 반환
        if k==0 or count<=1:
            return nums
        
        # 리스트 길이가 k보다 작을 경우
        if count < k:
            nums[:] = nums[count-(k%count):] + nums[:-(k%count)]
            return nums
            
        # 리스트 길이가 k보다 클 경우
        nums[:] = nums[-k:] + nums[:-(k%count)]
        return nums

Runtime : 152ms
Memory : 24.80 MB
Runtime과 Memory 모두 상위 80% 해당할 정도의 코드를 작성하게 되었다.

하지만 정말 주먹구구식으로 [테스트 케이스 실행 - 수정]을 반복하여 예외 값을 없애나간 탓에 리스트 슬라이싱 과정이 굉장히 복잡해졌다.

그리고 굉장히 많은 시간을 소요했으므로 실제 테스트 과정이었다면 시간 제약으로 풀지 못했을 것이다.

---

📝 Rotate Array 회고

역시 다양한 접근법들이 있었다. reverse()함수를 활용하여 나타낸 코드도 있었고, 나와 비슷하게 리스트 슬라이싱으로 접근한 방법도 많았다. 단지 차이점이 있다면 최종적으로 작성한 코드보다 훨씬 간단하게 표현할 수 있다는 것을 알게 되었다.

아마 똑같은 생각으로 접근을 했던 것 같은데, 여러 수정을 거치며 테스트 케이스에 맞추려고 작성한 탓에 본래의 의도를 조금 벗어나서 여러 조건들과 슬라이싱 방법에서 차이가 난 것 같다.

본래의 의도는 nums 리스트를 -k값 만큼 슬라이싱한 값에 이미 슬라이싱한 부분을 제외한 나머지 값들을 합치는 것이었는데 현재 코드를 보면 이 의도를 파악하기가 매우 힘들다. 같은 접근 방법을 사용한 코드들을 참고해보며 코드를 조금 더 간결히 수정해보았다.

class Solution(object):
    def rotate(self, nums, k):
        count = len(nums)
        
        if k==0 or count<=1:
            return nums
        
        nums[:] = nums[-k%count:] + nums[:-k%count]
        
        # nums=[1,2,3,4,5,6,7], k=3
        # nums[-k%count:] = [5, 6, 7]
        # nums[:-k%count] = [1, 2, 3, 4]

Runtime : 152ms ---> 133ms
Memory : 24.80 MB ---> 24.7 MB

수정 결과 본래 의도를 잘 나타내주는 간결한 코드가 되었고, Runtime은 19ms, Memory는 0.1MB의 성능 개선도 할 수 있었다. 수정의 핵심은 기존 리스트 길이가 k보다 크고 작을 경우를 지우고 모든 상황에서 적용되는 경우로 교체한 것이다.

k를 리스트 요소의 개수 만큼 나눈 나머지 값을 역순으로 슬라이싱 할 경우 k만큼 오른쪽으로 회전하는 값을 슬라이싱 할 수 있고, 그 반대로 슬라이싱 할 경우 오른쪽으로 회전되는 값들을 제외한 값을 슬라이싱 할 수 있었다.

또한 k가 0이거나 리스트의 요소 개수가 1보다 작은 경우에는 리스트가 그대로 반환되므로 해당 조건은 그대로 두어 리스트 슬라이싱 연산 과정을 거치지 않도록 했다.

처음 리스트 슬라이싱으로 접근했을 때는 슬라이싱 범위를 지정하는 것이 많이 헷갈렸던 것 같다. 수정 과정에서는 다른 사람들의 코드를 참고한 덕분에 비교적 쉽게 수정할 수 있었다.

이번 문제를 풀면서 느꼈던 점은 생각대로 코드의 결과가 나타나지 않았을 때, 테스트 케이스에 의존해서 맞추려는 습관이 있다는 것을 알았고 이는 전체 코드를 구성할 때 결코 좋지 않은 영향을 끼친다고 생각했다.

앞으로 알고리즘을 풀면서 이러한 점을 유의하며 개선할 수 있도록 노력해야겠다.