[leetcode] 11, 15, 20, 21

20. Valid Parentheses

https://leetcode.com/problems/valid-parentheses/

My Answer 1: Accepted (Runtime: 24 ms - 96.02% / Memory Usage: 14.4 MB - 34.96%)

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for i in range(len(s)):
            if s[i] == "(" or s[i] == "{" or s[i] == "[":
                stack.append(s[i])
            elif stack and s[i] == ")" and stack[-1] == "(":
                stack.pop()
            elif stack and s[i] == "}" and stack[-1] == "{":
                stack.pop()
            elif stack and s[i] == "]" and stack[-1] == "[":
                stack.pop()
            else:
                return False
        if stack:
            return False
        
        return True

여는 괄호들은 stack 에 쌓아주고
닫는 괄호를 만나면 stack[-1] 과 대응하는지 확인해서 유효한지 판단

짝을 찾지 못한 괄호가 stack 에 남아있으면 False

---

21. Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/

My Answer 1: Accepted (Runtime: 40 ms - 52.07% / Memory Usage: 14.2 MB - 85.43%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None and l2 is None:
            return l1
        if l1 is None and l2:
            return l2
        if l2 is None and l1:
            return l1
        
        a = ListNode(0, l1)
        prev = a
        while l1 and l2:
            if l1.val >= l2.val:
                prev.next = l2
                l2 = l2.next
                prev.next.next = l1
            else:
                l1 = l1.next
            prev = prev.next
        
        if l2:
            prev.next = l2
            
        return a.next

둘 다 None 일 때, 둘 중 하나만 None 일 때 예외 처리

l1 을 기준으로 잡아서 앞에 더미노드 추가해줌 (prev 쓰려고)
l2.val 가 l1.val 보다 작거나 같으면 l1 앞에 추가
크면 l1 을 이동

다 본 후에 l2 가 남아있으면 맨 뒤에 붙여줌 => prev.next = l2

---

11. Container With Most Water

https://leetcode.com/problems/container-with-most-water/

My Answer 1: Time Limit Exceeded (49 / 60 test cases passed.)

class Solution:
    def maxArea(self, height: List[int]) -> int:
        ans = 0
        for i in range(len(height)):
            for j in range(i+1, len(height)):
                h = min(height[i], height[j])
                ans = max(ans, h * (j-i))
        
        return ans

데자뷰의 향기.. 타임리밋 걸릴 걸 알았어요...

더 짧은 height 를 세로로, 인덱스 차이를 가로로 잡고 넓이 계산

전에도 소름돋게 똑같이 풀었다는 점~

Solution 1: Accepted (Runtime: 176 ms - 36.02% / Memory Usage: 16.5 MB - 53.05%)

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxarea = 0
        left = 0
        right = len(height)-1
        
        while(left < right):
            minheight = min(height[left], height[right])
            maxarea = max(maxarea, (right-left)*minheight)
            
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
                
        return maxarea

왼쪽 값이랑 오른쪽 값 중에 작은 값을 가진 애만 인덱스 이동

---

15. 3Sum

https://leetcode.com/problems/3sum/

My Answer 1: Time Limit Exceeded (315 / 318 test cases passed.)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return None
        
        nums.sort()
        
        ans = []
        for i in range(len(nums)):
            t = nums[i]
            for j in range(i+1, len(nums)):
                if -(nums[i] + nums[j]) in nums[j+1:]:
                    l = [nums[i], nums[j], -(nums[i] + nums[j])]
                    if l not in ans:
                        ans.append(l)
        
        return ans

nums 의 길이가 3 이상일 때만
이중 for 문으로 투썸부터 한 다음 "-투썸" 값을 찾아다가 ans 에 넣어줌

뭔가.. sort 하고 음수, 양수 파트 활용해서 푸는게 맞는거 같은데... 해결은 못함

Solution 1: Accepted (Runtime: 2384 ms - 29.61% / Memory Usage: 17 MB - 97.17%)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 0:
            return []
        
        nums.sort()
        
        result = set()
        
        for i in range(len(nums)):
            l = i+1
            r = len(nums)-1
            while l < r:
                three = nums[i] + nums[l] + nums[r]
                if three == 0:
                    result.add((nums[i], nums[l], nums[r]))
                    l += 1
                    r -= 1
                elif three < 0:
                    l += 1
                else:
                    r -= 1
    
        return list(result)

left, right 인덱스 이용하기

nums[i] 의 오른쪽을 두번째 for 문이의 범위로 설정

nums[i] + nums[l] + nums[r] 가 0 이면 result 에 추가
음수면 l + 1 해서 양수쪽으로 옮기고
양수면 r - 1 해서 음수쪽으로 옮기기