[leetcode 매일 풀기]25 reverse nodes in k group

오늘 리뷰할 문제는 reverse nodes in k group이다.

https://leetcode.com/problems/reverse-nodes-in-k-group/description/

Reverse Nodes in k-Group - LeetCode

 

input으로 linked list와 숫자 k가 주어졌을 때,

linked list를 순회하면서 k개의 node를 순회했을 때, 해당 node의 순서를 뒤바꾸어야 하는 문제이다.

아래 예제 그림을 보면 원하는 바가 조금 더 보인다.

 

문제를 들었을 때는, 엄청 간단해보이는데 왜 이게 난이도가 높지 하는 생각이 들었는데.

실제로 구현해보니 다양한 상황을 고려해야하는 문제여서 hard 난이도가 된 듯 했다.

구현 과정에서 테스트케이스를 짜두고 풀었는데, 디버깅에 시간을 투자하긴 했지만. 다행히 submission 한번에 해결하긴 했다.

 

아래는 내가 구현한 코드이다.

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __eq__(self, other):
        if not isinstance(other, ListNode):
            return False
        return self.val == other.val and self.next == other.next

    def __repr__(self):
        return f"{self.val}"


class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if k == 1:
            return head
        if head is None:
            return head

        prev_start_node = None

        curr_node = head
        iteration_count = 0
        result_node = head
        while curr_node is not None:
            curr_start_node = curr_node
            curr_next_node = curr_node.next
            for i in range(k):
                if curr_node is None or (curr_next_node is None and i < k - 1):
                    for j in range(i):
                        temp_node = curr_node.next
                        curr_node.next = curr_next_node
                        curr_next_node = curr_node
                        curr_node = temp_node
                    return result_node
                else:
                    if i == k - 1:
                        curr_start_node.next = curr_next_node
                        if prev_start_node:
                            prev_start_node.next = curr_node
                        if iteration_count == 0:
                            result_node = curr_node
                        prev_start_node = curr_start_node
                        curr_node = curr_next_node

                    else:
                        temp_node = curr_next_node.next
                        curr_next_node.next = curr_node
                        curr_node = curr_next_node
                        curr_next_node = temp_node
            iteration_count += 1

        return result_node


assert Solution().reverseKGroup(
    ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), 2
) == ListNode(2, ListNode(1, ListNode(4, ListNode(3, ListNode(5)))))
assert Solution().reverseKGroup(
    ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), 3
) == ListNode(3, ListNode(2, ListNode(1, ListNode(4, ListNode(5)))))
assert Solution().reverseKGroup(ListNode(1), 1) == ListNode(1)
assert Solution().reverseKGroup(ListNode(1, ListNode(2)), 2) == ListNode(2, ListNode(1))

 

이 문제에서 중요하다고 생각하는 건 결국 다르게 처리해야하는 상황들을 얼마나 잘 캐치할 수 있고, 그걸 깔끔하게 구현해내는지라고 생각했다. (특정 데이터 구조를 잘 아는 것 보다)

 

상황들을 나열해보자면

 

1. 기본 reverse 연결: 이 때는 node 두개와 temp node 한개로 reverse를 연결할 수 있다.
2. group이 끝나지 않았을 때: 1번을 다시 한번 돌리면 되는 것. 다만, group이 끝나지 않음을 판단하는 방법을 추가로 정의해야 한다.
3. 첫 시작인지 => 최종 return value를 어떻게 넣어줄 것인지를 결정해야함. reverse가 되었다면 마지막, 아니라면 처음으로
4. 중간에 있는 sequence인지: 중간에 있는 sequence라면 이전 시퀀스의 마지막을 현재 시퀀스의 처음과 이어주는 작업이 필요하다.

 

내 코드를 구현하고 난 뒤에도, 조금 더 깔끔하게 짤 방법이 없을지 고민하면서 다른 사람들 코드를 살펴본 느낌도 정리하자면

1. 코드가 깔끔하게 되어 있는 경우에는 그룹이 가능한지 여부를 체크하고 reverse하는 방법으로 만든다. (time complexity는 늘어나지 않는 수준)
2. recursion을 통해서 조금 더 깔끔한 느낌을 줄 수 있다.
3. 내 코드는 마지막에서 reverse를 한번 더 reverse하는 경우가 있다. n<=k 인 상황일 때 추가 코스트가 들긴 한다.
4. 다음번에 짠다면 나도 조건을 만족하면 reverse하는 식으로 짜야겠다. 왜냐하면 이게 이해하기 쉬워서 에러가 덜 나게 만드는 것 같고, 로직의 빈 틈을 찾기도 더 쉬울 듯 하다.