greentea31's Note

https://leetcode.com/problems/daily-temperatures/

풀이 과정

각 날짜의 온도가 주어질 때, 어떤 날짜에서 며칠을 기다려야 더 따뜻한 날이 되는지 출력하는 문제이다.

2중 for문 돌려서 O(N^2)로도 해결할 수 있겠지만, 스택을 활용해서 더 효율적으로 문제를 해결할 수 있다.

수의 index를 스택에 저장하면서, 스택탑의 index 날짜의 온도보다 더 따뜻한 날의 index가 들어오면 스택을 pop하면서 따뜻한 날의 index - 스택 탑의 index를 계산해서 정답 리스트에 저장해주면 문제를 해결할 수 있다. 

소스 코드

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        answer = [0 for _ in range(len(temperatures))]
        for a, b in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < b:
                last = stack.pop()
                answer[last] = a - last
            stack.append(a)
        return answer

https://leetcode.com/problems/remove-duplicate-letters/

풀이 과정

중복된 문자를 제거하되, 문자열을 사전식 순서로 나열하는 문제이다.

문제가 약간 이해하기 어려운데 set으로 중복 문자 없애고 sort로 정렬하라는 소리인가? 싶긴 하지만 예시를 보면 그렇지 않다. 2번 예시를 보자.

"cbacdcbc"가 예시로 주어져 있는데 여기에 단순히 ''.join(sorted(set(s))) 를 하게 되면 답이 'abcd'가 나오게 된다. 하지만 이 문제에서 원하는 정답은 acdb로 중복을 제거할 때 어떤 문자를 지우는지로 사전식 순서를 맞추되 문자의 위치를 옮기지는 않는 그런 방식을 요구하고 있다. 중복된 문자를 어떤 것을 지우는지에 따라 나올수 있는 것이 ['cbad', 'bacd', 'acbd'..]의 다양한 결과가 나올 수 있는데 이 중에서 사전식 순서로 맨 앞에 나와있는 것은 'acbd'니까 이것을 출력하라는 것이다.

사전상 앞에 있는 알파벳의 index를 찾고 거기서 문자열을 분리하고, 분리한 문자열에서 중복을 제거한 것이 원래 문자열에서 중복을 제거한 것과 같으면 정답에 분리 기준 문자를 추가하고... 를 재귀식으로 반복하는 방법으로 문제를 해결할 수 있다.

소스 코드

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        for char in sorted(set(s)):
            suffix = s[s.index(char):]
            if set(s) == set(suffix):
                return char + self.removeDuplicateLetters(suffix.replace(char, ''))
        return ''

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

풀이 과정

(, {, [, ), }, ]의 괄호가 주어질 때 주어진 문자열이 올바른 괄호 문자열인지 판단하는 문제이다.

스택으로 풀 수 있는 유명한 문제이다. 여는 괄호가 나왔을 때는 그냥 스택에 넣고 닫는 괄호가 나왔을 때는 스택 탑이 동일한 종류의 여는 괄호인지 확인하고 맞으면 스택 pop, 아니면 올바른 괄호 문자열이 아니므로 False를 리턴해주면 된다.

모든 문자열을 살펴봤을 때 스택이 비어있어야 한다. 스택이 비어있지 않으면 닫히지 않은 괄호가 존재하는 것이므로 올바른 괄호 문자열이 아니다.

소스 코드

class Solution:
    def isValid(self, s: str) -> bool:
        st = []
        for letter in s:
            if letter in ['(', '{', '[']:
                st.append(letter)
            elif letter == ')':
                if st and st[-1] == '(':
                    st.pop()
                else:
                    return False 
            elif letter == '}':
                if st and st[-1] == '{':
                    st.pop()
                else:
                    return False 
            elif letter == ']':
                if st and st[-1] == '[':
                    st.pop()
                else:
                    return False 
        return True if not st else False

https://leetcode.com/problems/odd-even-linked-list/

풀이 과정

1 -> 2 -> 3 -> 4 -> 5 -> 6을 1 -> 3 -> 5 -> 2 -> 4 -> 6과 같이 홀수 번째 링크드 리스트 이후에 짝수 번째 링크드 리스트가 오게 하는 문제이다.

홀수번째 인덱스와 짝수번째 인덱스를 가리키는 변수를 반복문으로 바꿔가면서 문제를 해결하였다.

소스 코드

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        odd = head
        even = head.next
        even_head = head.next
        
        while even and even.next:
            odd.next, even.next = odd.next.next, even.next.next
            odd, even = odd.next, even.next
        
        odd.next = even_head
        return head

https://leetcode.com/problems/swap-nodes-in-pairs/

풀이 과정

링크드 리스트를 2개씩 짝지어서 순서를 바꾸라는 문제이다.

중첩 함수 change를 재귀 함수로 사용하여 문제를 해결하였다.

소스 코드

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def change(prev, node):
            prev.next, node.next = node.next, prev
            if prev.next and prev.next.next:
                temp = prev.next
                prev.next = temp.next
                change(temp, prev.next)
        
        
        root = head
        if head and head.next:
            root = head.next
            change(head, head.next)
        return root

https://leetcode.com/problems/add-two-numbers/

풀이 과정

2개의 링크드 리스트를 더한 결과가 저장되어 있는 링크드 리스트의 head 포인터를 반환하는 문제이다.

carry를 이용해 받아올림을 구현하여 덧셈의 결과를 저장한 새로운 링크드 리스트를 만들었다.

소스 코드

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        root = head = ListNode(0)
        carry = 0
        while l1 or l2 or carry:
            sum_val = 0
            if l1:
                sum_val += l1.val
                l1 = l1.next
            if l2:
                sum_val += l2.val
                l2 = l2.next
            carry, val = divmod(sum_val + carry, 10)
            head.next = ListNode(val)
            head = head.next
        
        return root.next

https://leetcode.com/problems/reverse-linked-list/

풀이 과정

링크드 리스트를 뒤집는 문제이다.

링크드 리스트를 뒤집는 방법은 반복문으로 뒤집기, 재귀를 활용해서 뒤집기 2가지 방법이 가능하고 문제에서도 후속조치로 2가지 방법으로 모두 구현할 수 있냐고 묻고 있다.

재귀, 반복 2가지 방법으로 구현하였다.

소스 코드

재귀

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse(node, prev=None):
            if not node:
                return prev
            next, node.next = node.next, prev
            return reverse(next, node)
        return reverse(head)

반복

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        rev = None
        answer = []
        while head:
            rev, rev.next, head = head, rev, head.next
        return rev

https://leetcode.com/problems/palindrome-linked-list/

풀이 과정

링크드 리스트의 시작 포인터를 입력 받아서, 전체 링크드 리스트의 데이터가 팰린드롬인지 확인하는 문제이다.

팰린드롬이란 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬이라 한다.

문제를 해결하는 방법은 2가지가 떠오른다.

1. 링크드 리스트의 데이터들을 Deque에 전부 다 저장해놓고 Deque.popleft(), Deque.pop()을 해가면서 앞, 뒤 원소가 같은지 체크해가기.

2. 링크드 리스트를 2칸씩 뛰어가며 순회하는 fast, 1칸씩 뛰어가며 순회하는 slow를 두면 fast가 순회를 마치면 slow는 링크드 리스트의 절반까지 순회했을 것이라 기대할 수 있다. slow로 순회할 때 여태 순회했던 링크드 리스트의 원소를 역순으로 가지고 있는 새로운 링크드 리스트를 만들고, slow가 절반까지 순회했으면 절반 이후의 나오는 데이터들과 역순 링크드 리스트의 데이터가 같은지 아닌지를 확인하는 방법이 있다.

a -> b -> c -> b -> a의 링크드 리스트가 존재한다면,

fast: a -> c -> a

slow: a -> b -> c 순으로 순회가 진행되고 역순 링크드 리스트 c -> b -> a가 만들어진다. 전체 링크드 리스트의 중간부터의 링크드 리스트가 c -> b -> a 이고, 역순 링크드 리스트가 c -> b -> a이니 팰린드롬 문자열로 이루어진 링크드 리스트라고 판단할 수 있는 것이다.

소스 코드

deque 풀이

import collections

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        temp = collections.deque()
        while head.next is not None:
            temp.append(head.val)
            head = head.next
        temp.append(head.val)
        while len(temp) > 1:
            if temp.popleft() != temp.pop():
                return False
        return True

링크드 리스트 풀이

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        rev = None
        slow = fast = head
        
        while fast and fast.next:
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next
            
        if fast: # 길이가 홀수면
            slow = slow.next # 한칸 더
        
        while rev and rev.val == slow.val:
            slow, rev = slow.next, rev.next
        
        return not rev

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

풀이 과정

각 날짜별로 주식의 가격이 주어지는데, 싸게 사서 비싸게 팔때의 최대 이익을 구하는 문제이다.

각 날짜에서 현재 가격 - 가장 싸게 살수 있던 가격을 계산하면서 계산한 값중 가장 큰 값을 반환하면 된다.

소스 코드

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = 10001
        profit = 0
        for price in prices:
            min_price = min(price, min_price)
            profit = max(profit, price - min_price)
        return profit

https://leetcode.com/problems/product-of-array-except-self/

풀이 과정

배열을 입력받고, 각 배열의 원소에 대해 자기 자신을 제외한 나머지 원소의 곱의 배열을 구하는 문제이다.

문제를 읽고 나서 바로 드는 생각이라면 배열의 전체 원소를 곱해놓고 저장한 뒤, 각 배열의 원소를 나누면서 저장하는 방법일 텐데 이 방법은 다음과 같은 2가지 문제 때문에 안된다.

1. 배열에 0이 포함되어 있는 경우

    [3, 3, 0, 3, 3]이 입력일 때의 정답은 [0, 0, 81, 0, 0]이어야 하는데 전체 원소의 곱을 구해놓고 각 원소로 나누면 3번째 원소를 처리하기가 곤란해진다. 0 / 0 을 처리할 수가 없기 때문이다.

2. 문제에서 나누기 연산을 금지한다고 조건을 걸었음

    나누기 말고 다른 방법으로 풀어주기를 문제에서 원하고 있다.

DP로 문제를 풀 때 흔히 사용되는 누적합 배열을 만들어서 이 문제를 해결할 수 있다. 이 문제의 경우엔 누적합이 아니라 누적곱이다.

길이가 n+1인 입력이 들어왔을 때, d[i] = 0부터 i-1번째까지의 누적곱, d2[i] = n부터 i+1번째까지의 누적곱이라고 하면, answer[i] = d[i] * d2[i]가 성립한다.

위의 식을 사용해서 문제를 해결하였다. 근데 문제에서 메모리 최적화를 후속 조치로 요구했기에, d[i], d2[i]를 선언하지 않고 출력을 위한 answer 리스트만 선언한 뒤 for문 2번 돌려서 문제를 해결하였다.

소스 코드

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        answer = [1 for _ in range(len(nums))]
        product = 1
        for i in range(1, len(nums)):
            product *= nums[i-1]
            answer[i] *= product
        product = 1
        for i in range(len(nums)-2, -1, -1):
            product *= nums[i+1]
            answer[i] *= product
        return answer