오늘 뭐 개발하지?

문제 링크 : leetcode.com/problems/longest-substring-without-repeating-characters/

이 문제는 주어진 문자열에서 각 문자가 중복되지 않는 연속된 가장 긴 문자열의 길이를 반환하는 문제이다.

풀이방법

from collections import deque

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dq = deque()
        ans = ""
        for char in s:
            if char not in dq:
                dq.append(char)
                if len(ans) < len(dq):
                      ans = "".join(dq)
            else:
                if len(ans) < len(dq):
                      ans = "".join(dq)
                while True:
                    if dq.popleft() == char:
                        break
                dq.append(char)
        return len(ans)

이 문제는 스택을 이용하여 해결하였다. 스택에 문자를 하나씩 넣어두고 길이를 계산하여 최대 길이일 때만 정답을 갱신하고, 만약 중복된 문자가 나오면 스택에서 해당 문자가 나올 때 까지 이전 문자들을 제거하여, 스택에는 문자가 중복되지 않게 하였다. 문자열을 다 순회했을 때, 가장 길었던 정답의 길이를 반환한다.

문제 링크 : leetcode.com/problems/jewels-and-stones/

이 문제는 jewels에 있는 문자가 stones에 몇 개가 들어있는지 갯수를 반환하는 문제이다.

풀이방법

이 문제는 key, value 쌍 구조인 딕셔너리를 이용하여 해결하는 가장 기본적인 문제이다.
딕셔너리의 jewels를 dict에 입력해두고 stones에서 jewels에 있으면 count를 +1 하여 해결하였다.

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        dicts = {}
        for i in jewels:
            if i not in dicts:
                dicts[i] = 0
        for j in stones:
            if j in dicts:
                dicts[i] += 1
        return sum(dicts.values())

문제 링크 : leetcode.com/problems/merge-k-sorted-lists/

이 문제는 주어진 정렬된 linked list를 merge하여 하나의 linked list로 만드는 문제이다.

풀이방법

처음에는 n개의 linked list를 순회하여 가장 작은 값을 이전 값의 next로 연결하는 방식으로 구현하려고 했었는데 잘 되지 않아서 stack을 이용하는 방법으로 문제를 해결하였다. 처음엔 stack에 linked list의 node도 넣을 수 있나 싶었는데 역시 파이썬. 안되는 게 없다.

lists를 전부 순회하면서 각 linked list에 들어있는 요소들을 모두 stack에 저장한 후, lambda식을 이용하여 stack의 value를 기준으로 정렬한 후 각각의 node들을 연결시켜주었다.

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        head = ListNode()
        temp = head
        stack = []
        for i in lists:
            while i:
                stack.append(i)
                i = i.next
        stack = sorted(stack, key=lambda x:x.val, reverse=True)
        while stack:
            temp.next = stack.pop()
            temp = temp.next
        temp.next = None
        return head.next

문제 링크 : leetcode.com/problems/reorder-data-in-log-files/

이 문제는 주어진 logs 라는 배열을 주어진 조건에 맞게 정렬하는 문제이다.

주어진 조건은 다음과 같다.

1. 각 단어 뒤의 식별자는 소문자로만 구성된다. 또는,

2. 각 단어 뒤의 식별자는 숫자로만 구성된다.

정렬해야 하는 순서는

1. 식별자 뒤에 문자열이 오면(letter-logs) 사전순으로 정렬하고, 사전순이 같으면 식별자 숫자로 정렬한다.

2. 식별자 뒤에 숫자가 오면(digit-logs) Input되어있는 순서로 정렬되어야 한다.

3. 그 후, letter-logs 뒤에 digit-logs를 이어준다.

풀이방법

처음에는 위 조건대로 우선 letter-logs랑 digit-logs를 분리한 후, letter-logs를 lambda식을 이용하여 정렬하고, join으로 다시 하나의 문자열로 만들어 준 후에 letter-logs와 digit-logs를 합쳐주었다.

class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        split_list = []
        log_list = []
        dig_list = []
        ret = []
        for str in logs:
            s = str.split()
            if s[1].isdecimal():
                dig_list.append(s)
            else:
                log_list.append(s)
        sorted_log = sorted(log_list, key=lambda x: (x[1:], x[0]))
        for s in sorted_log:
            ret.append(" ".join(s))
        for s in dig_list:
            ret.append(" ".join(s))
        return ret

다른 풀이방법을 찾아보니 확실히 파이썬 답게 풀었구나 싶었다. split에 maxsplit parameter로 split할 수 있는 범위를 제한할 수 있는 것도 처음 알았고, return에서 조건문을 이렇게도 사용할 수 있구나 싶었다.

class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:

        def get_key(log):
            _id, rest = log.split(" ", maxsplit=1)
            return (0, rest, _id) if rest[0].isalpha() else (1, )

        return sorted(logs, key=get_key)

문제 링크 : leetcode.com/problems/reverse-string/

이 문제는 문자열을 Reverse 시키는 문제이다. 단, 주어진 문자열을 수정하여 공간복잡도가 O(1)이 되게 해야 한다.

풀이방법

파이썬에는 reverser() 라는 내장 메소드가 있다. list를 reverser 시켜주는 메소드이다.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        s.reverse()

문제 링크 : leetcode.com/problems/valid-palindrome/

이 문제는 문자열의 알파벳과 숫자의 배열이 Palindrome(문자열을 역순으로 해도 같은 문자열)인지 확인하면 되는 문제이다.

풀이방법

1. isalnum() 함수를 이용하여 특수문자를 제외해주고

2. 대소문자를 구문하지 않으므로 lower() 함수를 이용하여 소문자로 만들어서

3. Palindrome인지 확인한다.

Palindrome인지 확인하는 방법에는 여러가지가 있는데

1. start와 end를 이동하며 비교하기

2. pop(0) == pop()으로 비교하기

3. 중간부터 왼쪽과 오른쪽으로 가면서 비교하기

등이 있으나 파이썬에서는 list slicing을 이용해서 아주 쉽게 Palindrome을 확인할 수 있다.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = [i.lower() for i in s if i.isalnum()]
        return s == s[::-1]

아직 파이썬을 파이썬 답게 쓰지 못해서 s == s[::=1]같은게 되는 줄 몰랐다.

맨날 앞뒤 인덱스 비교해가면서 풀었는데 알아두면 참 좋은 테크닉인 것 같다.

문제 링크 : leetcode.com/problems/reverse-linked-list-ii/

이 문제는 m, n이 주어졌을 때, linked list의 m번째 노드부터 n번째 노드까지 역순으로 정렬하는 문제이다.

풀이방법

이번 문제는 주어진 범위의 list만 reverse하는 문제이다. 처음에는 주어진 범위의 list만 reverse하여 m-1 노드의 next를 rev 노드의 head에 연결하고, rev 노드의 tail 의 next를 n+1 노드에 연결하려 했지만 잘 되지 않아서 다른 방법을 찾았다. 이 방법은 이동하면서 start의 next를 end의 next로, end의 next를 end의 next.next로 연결하는 방법이다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if not head or m == n:
            return head
        root = ListNode()
        root.next = head
        start = root
        for _ in range(m - 1):
            start = start.next
        end = start.next
        for _ in range(n - m):
            temp = start.next
            start.next = end.next
            end.next = end.next.next
            start.next.next = temp
        return root.next

문제 링크 : leetcode.com/problems/odd-even-linked-list/

풀이방법

이 문제는 Linked list를 홀수번과 짝수번을 나눠서 정렬시키는 문제이다.
처음에는 노드를 swap해야 하나 싶었는데 다시 생각해보니 홀수, 짝수번째의 Node만 이어서 홀수번째 마지막을 짝수번째 시작 노드에 연결해주면 되는 문제였다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        # Linked list가 존재하지 않을 때 예외처리
        if not head:
            return None
        odd = head
        even_head = head.next
        even = even_head
        # even의 next가 없으면 list의 끝
        while even and even.next:
            odd.next = odd.next.next
            odd = odd.next
            even.next = even.next.next
            even = even.next
        # odd의 다음은 even의 시작
        odd.next = even_head
        return head

문제 링크 : leetcode.com/problems/swap-nodes-in-pairs/

이 문제는 linked list의 노드를 두 개씩 짝을 지어 swap한 후 head를 반환하는 문제이다.

풀이방법

swap은 짝수번째 마다 일어난다.

swap 후에는 홀수번째가 되므로 다음 노드로 이동한다.

head, mid, tail로 노드의 조건을 나뉘어서 swap하였다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        curr = prev = head
        while curr and curr.next:
            prec = curr.next
            # head
            if curr == head:
                head = curr.next
                curr.next = head.next
                head.next = curr
            # tail
            elif not curr.next.next:
                prev.next = prec
                curr.next = prec.next
                prec.next = curr
            # mid
            else:
                prev.next = curr.next
                curr.next = prec.next
                prec.next = curr
            prev = curr
            curr = curr.next
        return head

다른 풀이를 보니 head 앞에 root 노드를 만들어서 모든 노드에서 동일한 방식으로 swap이 가능하게 푼 방법도 있었다.

알고리즘 문제를 많이 풀어보질 않아서 이런 알고리즘 테크닉들을 익혀두면 알고리즘 문제들을 조금 더 general하게 풀 수 있을 것 같다.

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        root = prev = ListNode()
        prev.next = head
        while head and head.next:
            b = head.next
            head.next = b.next
            b.next = head
            
            prev.next = b
            
            prev = head
            head = head.next
            
        return root.next

문제 링크 : leetcode.com/problems/add-two-numbers/

이 문제는 두 linked list의 값들을 역순으로 하여 더한 결과의 역순을 linked list로 반환하는 문제이다.

풀이방법

두 linked list와 반환해야 할 linked list사이의 규칙을 찾아보면 역순으로 연결되어 있기 때문에 linked list의 시작이 가장 낮은 자릿수인 것을 알 수 있다. 따라서 두 linked list를 동시에 탐색하면서 값을 더하여 새로운 linked list를 만들면 되는 것이다.

sum_list.val = (l1.val + l2.val)
sum_list = sum_list.next

다만 여기서 주의해야 할 점은 l1.val + l2.val 의 값이 10을 넘었을 경우이다. 10을 넘었을 경우에는 다음 list에 값을 넘겨주어야 하므로 l1.val + l2.val 의 몫과 나머지를 따로 계산하여 몫은 다음 list로, 나머지는 value로 사용하면 된다.

remain_value = (l1.val + l2.val) // 10
sum_list = (l1.val + l2.val) % 10 # divmod 함수도 사용 가능
sum_list = sum_list.next
sum_list.val = remain_value

그리고 l1, l2의 조건에 맞게 코드를 정리하면 된다.

"""

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        sum_list = ListNode()
        curr = sum_list
        while l1 or l2:
            if not l1:
                remain_val = (curr.val + l2.val) // 10
                curr.val = (curr.val + l2.val) % 10
                l2 = l2.next
            elif not l2:
                remain_val = (curr.val + l1.val) // 10
                curr.val = (curr.val + l1.val) % 10
                l1 = l1.next
            else:
                remain_val = (curr.val + l1.val + l2.val) // 10
                curr.val = (curr.val + l1.val + l2.val) % 10
                l1 = l1.next
                l2 = l2.next
            if l1 or l2:
                curr.next = ListNode()
                curr = curr.next
                curr.val = remain_val
        # 마지막 자릿수 확인
        if remain_val == 1:
                curr.next = ListNode()
                curr = curr.next
                curr.val = remain_val
        return sum_list

다른 사람들의 코드를 보니 l1, l2가 동시에 존재할 때 먼저 while문을 돌리고, 그 다음 l1, l2 순서로 while문을 돌리는 쪽이 조금 더 가독성이 좋았다.