🧑🏻‍💻 LeetCode Medium Collections 2 - 20 Problems

0054. Spiral Matrix / 0739. Daily Temperatures

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        e,s,w,n = [0,1], [1,0], [0,-1], [-1,0]
        output = []
        rows, cols = len(matrix), len(matrix[0])
        visited = [[False] * cols for _ in range(rows)]
        cnt = 0
        x, y = 0,0
        dirs = [e,s,w,n]
        dir_i = 0
        while True:
            visited[x][y] = True
            output.append(matrix[x][y])
            cnt+=1
            if cnt == rows*cols:
                break

            nx,ny = x+dirs[dir_i][0], y+dirs[dir_i][1]
            #as it goes
            if 0<=nx<rows and 0<=ny<cols:
                if not visited[nx][ny]:
                    x,y=nx,ny
                    continue
            
            #change dir
            dir_i += 1
            if dir_i == 4: dir_i = 0
            nx,ny = x+dirs[dir_i][0], y+dirs[dir_i][1]
            x,y=nx,ny
            continue

        
        return output

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = [(temperatures[0],0)]
        answer = [0]*(len(temperatures))
        for x in range(1,len(temperatures)):
            temp = temperatures[x]
            while stack:
                if stack[-1][0] < temp:
                    popped = stack.pop()
                    answer[popped[1]] = (x-popped[1])
                else:
                    break
            stack.append((temp,x))
        return answer

 

🧑🏻‍💻 0054) 전형적인 시뮬레이션 문제. 방향 벡터 동 / 남 / 서 / 북 각각 만들고, dirs 리스트 만들어 넣는다. 방향 바꾸는 조건 (1) 배열의 끝까지 닿는 경우 + (2) 이미 방문한 곳을 방문한 경우: 이 2가지 조건만 만족하지 않는다면 x,y update / 그렇지 않는다면 dir 방향 바꿔서 확인.

 

🧑🏻‍💻 0739) 감소하는 monotonic stack을 유지하며 answer update하는 monotonic stack 유형

: 현재 위치에서 이후 원소 중 처음으로 증가하는 온도가 있을 때 그 사이의 날 수를 구하는 문제. 그러면 증가인지 알아보는 원소와, 날 수를 구하기 위해 각 원소의 index 정보까지 2개의 정보를 tuple로 저장해 구현하는 유형을 생각해야 한다. 증가일 경우 그 앞선 원소들(while stack)에서 넣고자 하는 원소보다 작은 숫자가 포함된 원소를 모두 차례대로 빼서 index간 차이로 날 수를 answer에 update. 결론적으로 온도가 감소하게끔 유지하게 만드는 monotonic stack 유형

---

0199. Binary Tree Right Side View / 0031. Next Permutation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        queue = deque()
        queue.append(root)

        while queue:
            qLen = len(queue)
            level = []
            for i in range(qLen):
                node = queue.popleft()
                if node:
                    level.append(node.val)
                    queue.append(node.left)
                    queue.append(node.right)

            if level:       
                ans.append(level[-1])

        return ans

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        l=len(nums)
        i=l-2
        
        #find the pivot
        while i>=0 and nums[i]>=nums[i+1]:
            i-=1

        if i>=0: #if pivot, swap
            j=l-1
            while nums[j]<=nums[i]: #find the rigthmost successor
                j-=1
            nums[i],nums[j] = nums[j],nums[i] #swap
            nums[i+1:] = reversed(nums[i+1:]) #reverse the suffix
            return nums
        else:
            #if no pivot
            #rearranged as the lowest possible order
            #(i.e., sorted in ascending order).
            nums = nums.sort()
            return nums

 

🧑🏻‍💻 0199) tree의 각 level 별 맨 오른쪽 node의 val을 모아 둔 ans update. BFS로 root부터 시작해 차례대로 내려가면서 queue의 개수가 곧 현재의 level내의 node 개수이므로(null 포함), popleft() 진행 후 if node일 때만 level에 실제 value 넣기. 한 level이 모두 끝나면 level list에 무언가 존재한다면 level[-1] append해서 누적 결과 ans 출력

 

🧑🏻‍💻0031) 유명한 조합론 <next permutation> 문제. 별도 포스팅 참조

---

0438. Find All Anagrams in a String / 0036. Valud Sudoku

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        from collections import Counter, defaultdict
        freq = dict(Counter(p))
        length = len(p)
        cur_freq = defaultdict(int)
        ans = []
        bf = 0
        for i in range(len(s)):
            cur_freq[s[i]] += 1
            if i == (length -1):
                if freq == cur_freq:
                    ans.append(i-len(p)+1)
            elif length <= i:
                cur_freq[s[bf]] -= 1
                if cur_freq[s[bf]] == 0:
                    del cur_freq[s[bf]]
                bf+=1
                if freq == cur_freq:
                    ans.append(i-len(p)+1)
        return ans

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        import collections
        cols = collections.defaultdict(set)
        rows = collections.defaultdict(set)
        squares = collections.defaultdict(set)

        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue
                if (board[r][c] in rows[r] or board[r][c] in cols[c] or board[r][c] in squares[(r//3, c//3)]):
                    return False
                cols[c].add(board[r][c])
                rows[r].add(board[r][c])
                squares[(r//3, c//3)].add(board[r][c])
        return True

 

🧑🏻‍💻 0438) sliding window 기법으로 현재 index부터 p length까지 cur_freq dict update하다가, p length index부터 맨 앞 문자 빈도수 1 감소 및 맨 오른쪽 문자 빈도수 1만 증가시킴으로써 O(N)으로 cur_freq dict update하며 원래 freq와 비교하며 맞을 때 index update.

 

🧑🏻‍💻 0036) 각 row와 col에 들어갈 숫자 set로 만들어서 rows와 cols dictionary 만들기. 추가로 squares라는 set가 들어간 dictionary 만들어서 squares도 update. squares는 현재 (r,c)에서 index 기준 squares의 (r//3,c//3)에 숫자를 넣는다.(9x9 정사각형 내에서 3x3 정사각형 영역)

---

0113. Path Sum II / 0189. Rotate Array

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        ans = []
        def dfs(node, l):
            if not node.left and not node.right: #if this is a leaf node
                if sum(l) == targetSum:
                    ans.append(l[:])
            else: #if this is not a leaf node
                if node.left:
                    l.append(node.left.val)
                    dfs(node.left,l)
                    l.pop()
                if node.right:
                    l.append(node.right.val)
                    dfs(node.right,l)
                    l.pop()        
        if root:
            dfs(root, [root.val])
        return ans

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k%=(len(nums))

        #reverse
        l,r = 0,len(nums)-1
        while l<=r:
            nums[l], nums[r] = nums[r], nums[l]
            l+=1
            r-=1
        
        #reverse first kth array
        l,r = 0,k-1
        while l<=r:
            nums[l], nums[r] = nums[r], nums[l]
            l+=1
            r-=1
        
        #reverse (k+1)th to the last-th array
        l,r = k,len(nums)-1
        while l<=r:
            nums[l], nums[r] = nums[r], nums[l]
            l+=1
            r-=1

        return nums

 

🧑🏻‍💻 0113) Easy Version 0112. Path Sum I과 동일 문제. 다만, leaf node까지의 경로의 합이 모두 targetSum하고 같을 때의 경로 계속 ans에 update. 전형적인 dfs backtracking 진행

 

* dfs(node, l) 진행

① return 조건) 해당 node가 leaf node라면, 만약 sum(l) == targetSum일 경우 list l 내의 모든 경로를 ans list에 그대로 update

 

② leaf node가 아닐 경우 해당 node의 left node / right node에 각각 value가 있고 없을 경우 확인해 dfs(node.left, l) / dfs(node.right, l) 각각 진행

: 동일 함수 위 내용엔 l.append() / 이후엔 l.pop()으로 앞 뒤 상황 backtracking 유형에 맞게 구현 지키기 꼭 기억

 

🧑🏻‍💻0189) k번 이동한 결과의 array를 in-place 알고리즘 방식으로 구하려면, 먼저 reverse를 진행한 뒤, index 기준 0 ~ k-1 / k ~끝까지의 각 subarray를 각각 reverse 진행한다. (in-place reverse이므로 양 끝에 투 포인터를 두어서 두 포인터가 만날 때까지 swap 진행)

---

0050. Pow(x,n) / 0560. Subarray Sum Equals K

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def get_pow(x,n):
            if n==0:
                return 1
            halved = get_pow(x,n//2)
            if n%2 == 0:
                return  halved * halved
            else:
                return halved * halved * x
        res = get_pow(x, abs(n))
        return res if n >=0 else 1/res

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        res = 0
        curSum = 0
        prefixSums = { 0 : 1}
        for n in nums:
            curSum += n
            diff = curSum - k 
            res += prefixSums.get(diff,0)
            prefixSums[curSum] = 1 + prefixSums.get(curSum,0)
            print(prefixSums)
        
        return res

 

🧑🏻‍💻 0050) Power by Divide & Conquer 유형.

① x^n을 구할 때 만약, n이 음수라면 x^(abs(n))을 구하고, 구한 결과를 res라 하면 1/res를 구하면 된다.

② x^n = x^(n/2) * x^(n/2)로 x^(n/2)를 구하면 x^n은 구한 결과를 제곱만 하면 되므로, O(logn) 시간 복잡도로 해결할 수 있다.

③ n을 2로 나누고 나누어 n이 0이 될 때까지(재귀이므로 return 조건 n == 0일 때 return 1) divide.

 

🧑🏻‍💻 0560) O(n)을 이용해서 부분 contiguous subarray의 합이 k가 되는 쌍의 개수 구하기. 

for문으로 O(n) 돌리면서, 현재 해당 원소를 끝으로 하는 contiguous subarray 중 합이 k가 되는 경우의 수를 누적으로 더해 나가면 된다. 아래 그림과 같이 원소 2일 때, 원소 2를 끝으로 하는 contiguous subarray는 {-3, -1, 4, 3, 1, 2}, {-1, 4, 3, 1, 2}, {4, 3, 1, 2}, {3, 1, 2}, {1, 2}, {2} 이렇게 있다. 이 때 각각의 array 각각의 합이 k가 되는 지 확인하려면 O(n^2) 소요. 이 때 아래 오른쪽 그림과 같은 발상을 생각해 볼 수 있다. 앞선 누적합의 결과를 hash map으로 저장하며 업데이트. 궁극적으로 index 0 부터 현재 원소 i까지의 누적합 - k인 diff만큼 해당되는 frequency(hash map indexing 결과)를 누적으로 더해주어야 된다. 그러면 hash map의 도움으로 O(n)만에 모든 contiguous subarray의 합이 k가 되는 경우의 수를 구할 수 있다.

 

* 아래 그림과 같이 부분 contiguous subarray의 합은 왼쪽 끝부터 현재까지의 contiguous subarray의 합에 앞선 왼쪽 끝부터 구하고자 하는 subarray의 앞 원소까지의 합을 뺀 것과 같다는 아이디어를 사용

 

---

0525. Contiguous Array / 0424. Longest Repeating Character Replacement

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        zero, one = 0,0
        res = 0

        diff_index = {} #diff(count[1] - count[0]) -> index

        for i, n in enumerate(nums):
            if n == 0:
                zero += 1
            else:
                one += 1
            if one - zero not in diff_index:
                diff_index[one - zero] = i
            
            if one == zero: #answer
                res = one + zero
            else:
                idx = diff_index[one - zero]
                res = max(res, i - idx)
        return res

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        res = 0

        l = 0
        maxf = 0
        for r in range(len(s)):
            count[s[r]] = 1 + count.get(s[r], 0)
            maxf = max(maxf, count[s[r]])

            while (r - l + 1) - maxf > k:
                count[s[l]] -= 1
                l += 1
            
            res = max(res, r-l+1)
        return res

 

🧑🏻‍💻 0525) hash map에 각 index i별 one-zero의 값을 저장해주면 된다. 이 때, 예를 들어 O(n)으로 for문을 돌리다가 index i에 one - zero가 3이라면, index i 보다 앞의 index j가 동일하게 one - zero가 3이라고 하자. 그러면 (i-j) 만큼의 원소 개수, 즉 index i+1부터 j까지의 subarray의 one 개수 = zero 개수라고 할 수 있다. 아래 그림을 참고하자.

: 맨 오른쪽 원소 1을 오른쪽 끝으로 갖고 있는 subarray 중 동등하게 0과 1을 같은 개수로 갖고 있는 최대 길이를 구하려고 한다. 그러면, one-zero가 2인 동일 위치는 두군데. O(n)으로 iteration 진행할 수록 기존 diff값이 diff_index key값에 존재하면 패스. 없을 때만 데이터를 넣음으로써 가장 긴 길이의 one-zero값의 길이를 보존한다.

 

🧑🏻‍💻 0424) 상당히 어려운 슬라이딩 윈도우 문제. for문으로 O(n)만큼 돌리며 freq count dictionary 업데이트. O(n)만큼 돌리며 슬라이딩 윈도우 길이가 길어지는데, 이 때 (슬라이딩 윈도우의 길이 - 업데이트 되는 max_frequency(maxf))가 k보다 작거나 같은 경우는 해당 슬라이딩 윈도우의 길이에 동일 character만 모두 넣을 수 있다는 뜻. 하지만, 그 반대로 k보다 크다면 해당 슬라이딩 윈도우 길이에 동일 character를 모두 넣을 수 없다. 따라서, 슬라이딩 윈도우의 l 왼쪽 포인터를 오른쪽으로 이동하면서 슬라이딩 윈도우 길이를 줄이며 업데이트. l과 r 왼쪽 오른쪽 포인터로 이루어진 슬라이딩 윈도우: r을 오른쪽으로 움직이면서 최대한 res 정답 최댓값을 찾고, 더 이상 찾을 수 없다면 l을 오른쪽으로 움직이면서 슬라이딩 윈도우 길이 조절.

 

---

0007. Reverse Integer / 0074. Search a 2D Matrix

class Solution:
    def reverse(self, x: int) -> int:
        if x>0:
            value=int(str(x)[::-1]) #reversed
        else: 
            value=-1*int(str(x*-1)[::-1])  #reversed
        
        if value not in range(-2**31,2**31): #Overflow 
            value=0
            
        return value

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row, col = len(matrix), len(matrix[0])
        target_in_a_row = -1
        for x in range(row):
            if target < matrix[x][0]:
                break
            target_in_a_row = x
        if target_in_a_row == -1:
            return False
        l = matrix[target_in_a_row]
        
        start, end = 0, len(l)-1
        while start<=end:
            mid = (start+end)//2
            if target == l[mid]:
                return True
            elif target < l[mid]:
                end = mid - 1
            else:
                start = mid + 1
        return False

 

🧑🏻‍💻 0007) 쉽게 [::-1]로 reverse slicing

 

🧑🏻‍💻 0074) 먼저 target이 몇번째 행에 포함되어 있는 지 확인(몇번째 행인지 포함 모르면 False 리턴) / 그 다음, 포함된 행을 이분 탐색으로 돌려 target의 여부 확인. 이미 정렬된 행이므로 정렬 없이 바로 진행. 

---

0179. Largest Number / 0016. 3Sum Closest

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums = list(map(str, nums))
        nums.sort(key=lambda x: x*10, reverse=True)
        return str(int(''.join(nums)))

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = nums[0] + nums[1] + nums[2]
                
        for i in range(len(nums)-2):
            l, r = i+1, len(nums)-1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s == target:
                    return s
                if abs(s - target) < abs(res - target):
                    res = s
                if s < target:
                    l += 1
                else:
                    r -= 1
                            
        return res

 

🧑🏻‍💻 0179) 주어진 리스트 내의 여러 숫자를 10번 반복해서 사전순 정렬. 즉 맨 앞의 숫자를 비교해 확인. 예를 들어 3과 34를 비교한다면 334와 343이 되는데 34가 먼저 오고 3이 그 다음 오는 게 맞다. 이를 판단하기 위해서는 3을 10번 반복한 결과 / 34를 10번 반복한 결과 중 사전 순 앞서는 걸 확인. 3을 10번 반복한게 사전 순 앞서므로 사전 순 뒤(reverse=True)의 문자열을 먼저 오게 한다. 즉 동일 문자열을 10번 반복하게 해서 정렬을 할 수 있다.

 

🧑🏻‍💻 0016) i 고정하고, j와 k 투 포인터를 i+1부터 len(nums)-1까지 돌리면 된다. 한 개 포인터 고정하고 쭉 나머지 돌리는 투 포인터 방식 동일.

---

0227. Basic Calculator II / 0019. Remove Nth Node From End of List

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        mul, share = False, False
        ans = 0
        real_s = []
        for character in s:
            if character != ' ':
                if not real_s:
                    real_s.append(character)
                else:
                    if character in ['-','+','*','/']:
                        real_s.append(character)
                    else:
                        if real_s[-1] in ['-','+','*','/']:
                            real_s.append(character)
                        else:
                            real_s.append(real_s.pop()+character)
        for character in real_s:
            if character.isdigit():
                if mul:
                    stack.append(int(stack.pop())*int(character))
                    mul = False
                elif share:
                    stack.append(int(stack.pop())//int(character))
                    share = False
                else:
                    stack.append(character)
            else:
                if character == '*':
                    mul = True
                elif character == '/':
                    share = True
                else:
                    stack.append(character)
        while stack:
            popped = stack.pop()
            if str(popped).isdigit():
                popped = int(popped)
                tmp = popped
            else:
                if popped == '-':
                    ans += (-tmp)
                else:
                    ans += tmp
        ans+=int(popped)
        return ans

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        #get length
        node = head
        length = 1
        while node.next != None:
            node = node.next
            length+=1

        #remove order-th node
        order = length - n
        node = head
        before = None
        order_i = 0

        while node != None:
            if order_i == order:
                if before == None:
                    head = node.next
                else:
                    before.next = node.next
                break
            before = node
            node = node.next
            order_i+=1
            
        return head

 

🧑🏻‍💻 0227)

① '33 /   319 +2-1'과 같은 exp가 있다면 띄어쓰기 모두 생략하고, 숫자는 숫자끼리 먼저 붙여서 real_s 만들기

② 일단 *와 /만 먼저 진행되므로 +와 -는 그대로 넣고, *와 /인 경우만 연산해서 먼저 stack 완성

ex) '33*2+3'이 있다면 '66+3'으로 바꾼다.

③ '3+1-2'와 같이 +와 -만 구성된 stack에서 거꾸로 앞에 부호가 +라면 popped를 그저 더하고, -라면 -popped를 더한다. 그리고 맨 앞에 남은 숫자는 while stack 종료 이후 ans += int(popped) 연산으로 ans update → return ans

 

🧑🏻‍💻 0019)

① 먼저 head 첫번째 노드 node부터 node.next != None일 때까지 한 바퀴 계속 돌리면서 node = node.next로 업데이트하며(즉, linked list를 돌리며) length += 1로 linked list의 전체 길이 length 구하기

② 그러면 order(length - n)번째의 node를 제거하기. order_i = 0이라는 변수를 정해 order_i == order일 때 해당 노드를 제거하고 앞과 뒤의 노드를 연결하는 아이디어를 생각해야 한다. 현재 node의 앞의 node를 before라고 하면, 앞의 노드가 현재 node의 뒤의 노드와 연결하게 해주면 된다.

 

(1) before node가 존재할 경우: 아래와 같이 before.next =node.next

(2) before node가 존재하지 않을 경우(즉, 현재 node가 맨 앞의 node일 경우): 아래와 같이 node.next가 맨 앞의 head가 되므로 head = node.next

③ 계속 while문을 돌리면서 before, node, order_i가 업데이트 되어야 하므로 before = node / node = node.next / order_i += 1 코드

---

0328. Odd Even Linked List / (★) 0024. Swap Nodes in Pairs

# 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: Optional[ListNode]) -> Optional[ListNode]:
        order = 0
        odd_head = None
        odd_before = None
        even_head = None
        even_before = None
        cur_node = head
        
        while cur_node != None:
            if order == 0:
                even_head = cur_node
                even_before = cur_node
            elif order == 1:
                odd_head = cur_node
                odd_before = cur_node
            else:
                if order%2==1:
                    odd_before.next = cur_node
                    odd_before = cur_node
                else:
                    even_before.next = cur_node
                    even_before = cur_node

            order+=1
            cur_node = cur_node.next
            if even_before:
                even_before.next = None
            if odd_before:
                odd_before.next = None
        
        cur_node = even_head
        if cur_node:
            while cur_node.next != None:
                cur_node = cur_node.next
            cur_node.next = odd_head
        return even_head

# 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: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev, curr = dummy, head

        while curr and curr.next: #need at least two nodes
            #save ptrs
            nxtPair = curr.next.next
            second = curr.next

            #reverse this pair
            second.next = curr
            curr.next = nxtPair
            prev.next = second

            #update ptrs
            prev = curr
            curr = nxtPair
        
        return dummy.next

 

🧑🏻‍💻 0328)

** Space Complexity O(1)로 쉽게 odd number nodes와 even number nodes 각각 연결해야 한다.

① odd용 linked list와 even용 linked list를 기존 linked list에서 각각 쪼개기 아이디어.

② 첫번째와 두번째 node 도달 시 even_before, even_head / odd_before, odd_head 각각 초기화

③ 세번째 이상의 node 도달 시 even node라면 even_before.next = cur_node로 연결. 그리고 even_before를 cur_node로 update / odd node도 마찬가지

④ (**주의) cur_node update 후 업데이트 되는 even_before / odd_before의 next 값을 None으로 바꾸어 짝수 node의 경우 node 4 -> node 5가 연결되지 않도록 두 종류의 before를 지속적으로 update

⑤ odd_head와 even_head 두 종류의 linked list 만들어졌다면, even_head linked list를 while문으로 돌려 even_head linked list 맨 오른쪽 node로 cur_node pointer 옮기기. 그리고 옮겨진 최종 cur_node의 next를 odd_head로 설정해 두 linked list 연결하면 끝!

 

🧑🏻‍💻 0024) pair 기준 reverse 문제이므로 두 칸 씩 움직이며 swap하면 되는 idea를 생각해야 하는 문제.

① 현재 curr 기준 바로 앞 node를 prev, 바로 뒤 node를 second, 뒤의 뒤의 node를 nxtPair라 하자(while curr and curr.next라 하였으므로 pair로 존재하는 경우만 while문 돌릴 수 있다)

② prev -> second / second -> curr / curr -> nxtPair 이렇게 세 포인터를 각각 다른 node로 가리키게 방향을 업데이트

③ prev, curr update

* 맨 앞에 dummy ptr 아이디어를 생각해 내 총 3개의 연결 줄을 바꿔야 한다는 아이디어가 중요

---