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

# Valid Palindrome

[Quetion]

LeetCode 125. Valid Palindrome

📌 접근법

[문제 이해]

• 문자열에서 영문, 숫자가 아닌 것을 제외하고, 모두 소문자이어야 한다.
• 앞 뒤로 동일하게 읽히는 데칼코마니 문자열이어야 한다.

데칼코마니 = 맨 앞과 맨 뒤의 문자열을 비교해서 같으면 된다로 이해했다.
그래서 투포인터 방법으로 문제를 해결하면 되겠다고 생각했다.
생각흐름은 다음과 같다.

1. 모두 소문자로 변환한다
2. a-z까지 해당 할 경우 새로운 변수에 문자할당
3. left, right 포인터 생성
4. l과 r의 위치에 해당하는 문자열 비교 같으면 l=증가 r=감소
5. 틀리면 false

💻 구현

class Solution(object):
    def isPalindrome(self, s):
        s=s.lower()
        new=""
        
        for i in s:
            if i.isalnum():
                new+=i
        
        r=len(new)-1
        for l in range(len(new)):
            if l >= r:
                break

            if new[l] != new[r]:
                return False
            
            r-=1
        
        return True

Runtime: 295ms | Memory: 16.5MB
LeetCode 코드 중 Runtime 21%, Memory 8% 해당하는 결과

lower() 함수를 활용하여 대문자를 소문자 변환
isalnum() 함수로 문자열이 영문과 숫자인지 확인

📝 Valid Palindrome 회고

• new라는 새로운 변수를 생성해서 n만큼 for문을 돌고 저장하므로 O(n)의 공간복잡도를 가지고 있다.
• O(n)의 시간복잡도를 가지고 있지만, 두번의 for문을 거치므로 사실상 O(2n)의 시간복잡도를 가진다.

새로운 변수에 영문, 숫자만 담는 과정을 없애고 소문자를 변환하는 과정을 조건문에 더한다면, for문 1개와 변수 1개를 없앨 수 있으므로 시간복잡도 O(n), 공간복잡도 O(1)로 개선할 수 있을 것 같다.

class Solution(object):
    def isPalindrome(self, s):
        l,r=0,len(s)-1

        while l < r:
            if not s[l].isalnum():
                l+=1

            elif not s[r].isalnum():
                r-=1

            elif s[l].lower() != s[r].lower():
                return False
            
            else:
                l += 1
                r -= 1
        
        return True

Runtime: 295ms ---> 24ms
Memory: 16.5MB ---> 14.87MB

기존 isalnum()함수로 for문을 돌려 새로운 변수에 저장하는 방법을 제거하고, l포인터와 r포인터를 활용하여 조건문에 할당했다.

또한 조건문을 통해 비교할 문자 값만 소문자로 변경하여 비교함으로써 전체를 소문자로 바꾸는 과정도 없앨 수 있었다.

결론적으로 Runtime과 Memory 모두 눈에 띄게 개선할 수 있었고, 이 방법으로 접근했을 때 해당 문제는 for문 보다는 while문으로 변경하니 더 깔끔한 것 같다.

---

# Two Sum II - Input Array Is Sorted

[Quetion]

LeetCode 167. Two Sum II - Input Array Is Sorted

📌 접근법

[문제 이해]

• 리스트는 오름차순으로 정렬되어 있다.
• 리스트의 값 중 두개의 합이 target값과 같으면 해당 값들의 인덱스+1을 반환해야 한다.
• 반환 값은 리스트 형식이다.

투포인터 접근 방법으로 생각했다.
두개의 포인터를 증감 시켜서 target값과 일치하면 결과 리스트에 추가하고 결과 리스트를 반환하면 되겠다고 생각했다.
이를 의사코드화 해보았다.

1. left, right 포인터 활용

2. 리스트[l] + 리스트[r] > target이면,
   right 포인터 감소

3. 리스트[l] + 리스트[r] < target이면,
   left 포인터 증가

4. 리스트[l] + 리스트[r] == target
   result.append(l+1)
   result.append(r+1)

5. result 반환

💻 구현

class Solution(object):
    def twoSum(self, numbers, target):
        i=0
        l,r=0,len(numbers)-1
        result=[]
        
        while numbers:
            if l >= r:
                break

            if numbers[l] + numbers[r] > target:
                r-=1

            elif numbers[l] + numbers[r] < target:
                l+=1

            else:
                result.append(l+1)
                result.append(r+1)
                break
            
            i+=1
        return result

Runtime: 93ms | Memory: 14MB
LeetCode 코드 중 Runtime 67%, Memory 84% 해당하는 결과

시간복잡도는 O(n), 공간복잡도는 O(1)을 가지고 있다.

📝 Valid Palindrome 회고

• if >= r: break를 while문 조건으로 변경한다면 지울 수 없앨 수 있을 것 같다.
• result라는 변수를 생성하지 않고 결과 값을 반환한다면 더 나은 방법이 될 수 있을 것 같다.
• 이진 검색 방법으로 접근하면 시간복잡도를 O(n)에서 O(nlogn)으로 개서할 수 있을 것 같다.

# 불필요한 if문, result 변수 제거

class Solution(object):
    def twoSum(self, numbers, target):
        l,r=0,len(numbers)-1
        
        while l <= r:
            if numbers[l] + numbers[r] == target:
                return [l+1, r+1]
                
            elif numbers[l] + numbers[r] < target:
                l+=1
                
            else:
                r-=1

Runtime: 93ms ---> 88ms
Memory: 14MB ---> 14MB

불필요한 if문과 result변수를 제거하고 append()함수를 사용하지 않았다고 해서 5ms의 Runtime 개선은 있지만 효과가 미미했다. 성능적으로 크게 영향을 끼치지는 않았지만 코드가 간결해지는 효과는 얻을 수 있었다.

# 이진 검색 방법으로 접근법 변경
class Solution(object):
    def twoSum(self, numbers, target):
        for i in range(len(numbers)):
            check = target-numbers[i]    
            l,r=i+1,len(numbers)-1
            
            while l <= r:
                avg = (l+r)//2
                if numbers[avg] == check:
                    return [i+1, avg+1]
                
                elif numbers[avg] > check:
                    r = avg-1
                else:
                    l = avg+1

Runtime: 93ms ---> 137ms
Memory: 14MB ---> 14.7MB

이진검색의 방법으로 코드를 구현해보았는데 이상하게도 처음 접근법에 비해 Runtime과 Memory에서 더 좋지 않은 결과를 얻었다. 분명 이진검색의 경우 시간복잡도가 O(nlogn)으로 기존 O(n)에 비해 빨라야 된다고 생각해서 다른 솔루션들을 참고해보았다.

그 결과 현재 이진검색으로 구현한 코드에서는 한번 탐색했던 요소를 다시 탐색하는 상황이 있었고, 그렇게 될경우 O(nlogn)이 아닌 반복문 두개의 O(n^2)에 더 가깝다고 할 수 있으므로 느렸던 것이다.

# 중복 탐색 확인 duplicate list 추가
class Solution(object):
    def twoSum(self, numbers, target):
        duplicate = []
        
        for i in range(len(numbers)):
            
            if not numbers[i] in duplicate:
                duplicate.append(numbers[i])

                check = target-numbers[i]    
                l,r=i+1,len(numbers)-1
            
            while l <= r:
                avg = (l+r)//2
                if numbers[avg] == check:
                    return [i+1, avg+1]
                
                elif numbers[avg] > check:
                    r = avg-1
                else:
                    l = avg+1

Runtime: 137ms ---> 85ms
Memory: 14.7MB ---> 14.7MB

duplicate라는 list를 추가하여 이미 탐색한 값인지 확인하는 조건문을 추가해줌으로써 중복 탐색의 경우를 배제했다.

결과적으로 가장 처음인 93ms 보다도 더 빠른 Runtime을 가질 수 있었고, 8ms의 Runtime 개선효과를 얻을 수 있었다. 하지만 duplicate라는 리스트에 값을 저장하는 상황을 추가하여 공간복잡도는 더 높아졌다.

---