Coding_Quiz_Python_1

1. Two Sum

Link : https://leetcode.com/problems/two-sum/description/?difficulty=EASY

Hash Map (딕셔너리 이용)

보조 공간을 이용해 빠르게 차이를 찾는 방식.

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_map = {}

        for index, num in enumerate(nums):
            diff = target - num

            if diff in num_map:
                return [num_map[diff], index]
            
            num_map[num] = index

Sorting + Two Pointers (정렬 + 투 포인터)

정렬 후 양 끝에서 합을 비교.

• 시간 복잡도: O(n log n)
• 공간 복잡도: O(n)

def twoSum(self, nums: List[int], target: int) -> List[int]:

    arr = [(num, i) for i, num in enumerate(nums)]
    arr.sort()

    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left][0] + arr[right][0]
        if s == target:
            return [arr[left][1], arr[right][1]]
        elif s < target:
            left +=1
        else:
            right -=1

2. Add Two Numbers

Link : https://leetcode.com/problems/add-two-numbers/description/?difficulty=EASY

def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], c=0) -> Optional[ListNode]:
    sum_ = l1.val + l2.val + c
    remain = sum_ % 10
    carry = sum_ // 10

    new_node = ListNode(remain)

    if l1.next != None or l2.next !=None or carry != 0:
        if l1.next == None:
            l1.next = ListNode(0)
        if l2.next == None:
            l2.next = ListNode(0)
        new_node.next = self.addTwoNumbers(l1.next, l2.next, carry)
    return new_node

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        current = dummy
        carry = 0

        while l1 or l2 or carry:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0

            total = val1 + val2 + carry
            remain = total % 10
            carry = total // 10

            current.next = ListNode(remain)
            current = current.next

            if l1: l1 = l1.next
            if l2: l2 = l2.next

        return dummy.next

3. Longest Substring Without Repeating Characters

Link : https://leetcode.com/problems/longest-substring-without-repeating-characters/description/?difficulty=EASY

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_num = 0
        temp = []

        for i in range(len(s)):
            while s[i] in temp:
                temp.pop(0)
            
            temp.append(s[i])
            max_num = max(len(temp), max_num)

        return max_num

투 포인터 + set

• 같은 슬라이딩 윈도우인데 set으로 포함 여부를 O(1)에 체크.
• 왼쪽 포인터(left)를 움직이며 중복을 제거.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_num = 0
        left = 0
        temp = set()

        for right, ch in enumerate(s):

            while ch in temp:
                temp.remove(s[left])
                left += 1
            temp.add(ch)

            max_num = max(max_num, len(temp))
        return max_num

5. Longest Palindromic Substring

Link : https://leetcode.com/problems/longest-palindromic-substring/?difficulty=EASY

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) <= 1:
            return s
        
        def expand(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right +=1
            return s[left+1 : right]
        max_str = s[0]

        for i in range(len(s)-1):
            odd = expand(i, i)
            even = expand(i, i+1)

            if len(odd) > len(max_str):
                max_str = odd
            if len(even) > len(max_str):
                max_str = even
        return max_str

class Solution:
    def longestPalindrome(self, s: str) -> str:

        if len(s) < 2:
            return s

        def expand(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # valid palindrome is s[left+1 : right] (right is exclusive)
            return left+1, right
        max_str = ''
        for i in range(len(s)):
            l1, r1 = expand(i, i)
            l2, r2 = expand(i, i+1)

            odd_str = s[l1:r1]
            even_str = s[l2:r2]

            if len(odd_str) > len(max_str):
                max_str = odd_str
            if len(even_str) > len(max_str):
                max_str = even_str
        return max_str

6. Zigzag Conversion

Link : https://leetcode.com/problems/zigzag-conversion/description/?difficulty=EASY

class Solution:
    def convert(self, s: str, numRows: int) -> str:

        if numRows == 1 or numRows >= len(s):
            return s
        
        rows = [[] for row in range(numRows)]

        index = 0
        step = 1
        for char in s:
            rows[index].append(char)

            if index == 0:
                step = 1
            elif index == numRows-1:
                step = -1
            
            index += step

        for i in range(numRows):
            rows[i] = ''.join(rows[i])
    
        return ''.join(rows)