greentea31's Note

https://leetcode.com/problems/implement-stack-using-queues/

풀이 과정

큐로 스택을 구현하는 문제이다. 큐 2개로 스택을 구현하라고 하고 있고, 후속조치로 큐 1개로 스택을 구현해달라고 하고 있다.

1. 큐 2개로 구현하기

pop 할 때 스택에서 맨 처음 나오는 값이 큐에서는 제일 마지막에서 나오는 값일 것이므로, push 받을 때는 입력받은 값을 그냥 큐에 넣어주면 된다. pop 받을 때는 큐의 길이 - 1만큼 다른 큐에 원소들을 빼고 마지막 하나 남은 값을 pop 해주면 된다. top을 받았으면 마지막 하나 남은 값을 반환해주고 다시 큐에 넣어주면 된다. 스택이 비어있는지 판단하려면 큐 2개가 전부 비어있으면 스택도 비어있는 것이고, 아니면 스택에 원소가 있는 것이다.

2. 큐 1개로 구현하기

pop할 때 스택에서 맨 처음 나오는 값이 큐에서는 제일 마지막으로 나오는 값임을 생각하며 그냥 push 받을 때 push 받은 값이 큐의 맨 앞으로 가게 조작해주면서 스택의 기능을 하게 할 수 있다. 일단 입력받은 값을 큐에 넣고 큐의 사이즈 - 1번만큼을 앞에서 빼준 다음에 다시 뒤에 붙여주면 된다.

예시)

1, 2, 3이라는 큐에서 4를 입력받으면

1, 2, 3 -> 1, 2, 3, 4 -> 2, 3, 4, 1 -> 3, 4, 1, 2 -> 4, 1, 2 3

pop()하면 4가 나올 것이고 나중에 입력받으면 먼저 나오는 스택이 구현됨.

소스 코드

큐 1개로 구현한 코드이다.

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]
        

    def empty(self) -> bool:
        return True if len(self.q) == 0 else False

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