Leetcode - 1457. Pseudo-Palindromic Paths in a Binary Tree

문제 링크

1457. Pseudo-Palindromic Paths in a Binary Tree

문제 개요

한 BinaryTree인 TreeNode가 주어진다. 경로를 따라 Leaf-Node까지 도달하면 해당 경로가 pesudo-palindromic 인지 판단해야 한다.

pesudo-palindromic이란, 한 배열의 순열이 앞 또는 뒤부터 읽어도 순서가 같은(palindromic) 배열이다.

예를 들어, [1,2,1]은 앞에서 읽어도 121 뒤부터 읽어도 121이므로 pesudo-palindromic이다.

다른 예제로 [2,2,4]도 pesudo-palindromic이다. [2,2,4]의 순열 중 [2,4,2]가 앞에서 읽어도 242 뒤부터 읽어도 242로 동일하기 때문이다.

문제의 목표는 한 TreeNode를 탐색하여 pesudo-palindromic의 개수를 구하는 것이다.

각 Node의 Value는 1 ~ 9 까지의 정수이다.

입력 예제

아래의 그림의 TreeNode의 정답은 2이다.

[2,3,3]

[2,3,1]

[2,1,1]

TreeNode의 leftNode까지의 탐색은 총 3개가 있다.

그 중 [2,3,3] 과 [2,1,1]의 순열이 각 323, 121이고 231은 palindromic이 될 수 없기 때문이다.

문제 분석

1. TreeNode의 탐색 방법

TreeNode는 leafNode로 도달해야 한다.

BinaryTree의 탐색 방법은 Graph의 탐색방법인 DFS와 BFS로 나뉘어 진다.

탐색 방법의 차이점은 아래의 [그림 2]와 같다. DFS는 root Node에서 부터 leaf Node로 우선적으로 탐색하고 BFS는 rootNode에서 height level별로 탐색하게 된다.

따라서 해당 문제는 DFS의 방식대로 제일 위의 Node인 Root-Node부터 Leaf-Node까지 도달하기 위한 경우의 수를 먼저 구해야 한다.

2. pesudo-palindromic의 특징

경로는 DFS를 이용해 구했다면, 다음은 pesudo-palindromic이 어떤 특징이 있는지 확인해야 한다.

pesudo-palindromic는 해당 경로의 순열이면 되기 때문에 경로의 순서는 중요하지 않고 경로 안에 있는 Node-Value에 따라 판단할 수 있다.

pesudo-palindromic이 될 수 있는 경로는 Node-Value들의 개수가 1개만 홀수이거나 아니면, 전부 짝수여야 한다.

따라서, Node-Value의 개수가 홀수인 item이 2개 이상이면, pesudo-palindromic이 아니게 된다.

pesudo-palindromic의 경우

path가 홀수일 때 = [1,2,1]
유일하게 중복이 없는 수 => 2

path가 짝수일 때 = [1,1,2,2]
중복이 없는 수 => 존재하지 않아야 함

해결 전략

DFS 사용

TreeNode를 DFS를 이용하여 경로를 구한 후, Leaf-Node까지 도달할 때, pesudo-palindromic을 판단하기 위한 코드는 아래와 같다.

DFS는 Stack을 이용하여 구했다.

class TreeNode:
    def __init__(val:int, left:TreeNode, right: TreeNode):
        self.val = val
        self.left = left
        self.right = right

# PathStore는 상태값을 저장하지 않는 Immutable Object 이다
class PathStorage(metaclass=ABCMeta):
    @abstractmethod
    def addPath(node: TreeNode):
        pass

    @abstractmethod
    def is_pesudo_palindromic() -> bool:
        pass

def DFS(root:TreeNode, path: PathStorage):
    stack = [(root, path.addPath(root))]
    answer = 0
    while stack:
        node, path = stack.pop()
        if node.left == None and node.right == None:
            if path.is_pesudo_palindromic():
                answer += 1

        if node.left:
            stack.append((node.left, path.addPath(node.left)))

        if node.right:
            stack.append((node.right, path.addPath(node.right)))

    return answer

path를 저장하기 위한 기본 골격은 완성되었다. PathStorage()를 어떻게 완성하느냐에 따라 성능이 달라진다.

List 사용

path를 저장하기 위해 바로 떠올리는 방법인 List를 이용해 관리할 수 있다. PathStorage를 상속받아 List기반의 Storage를 구축하면 아래와 같이 나타난다.

class PathByListStorage(PathStorage):
    def __init__(self, storage:List[int] = []):
        self.storage = storage

    def addPath(self,node: TreeNode):
        return PathByListStorage(self.storage + [node.val])

    def is_pesudo_palindromic(self) -> bool:
        odd_count = 0
        for item in range(1,10):
            if self.storage.count(item) % 2 == 1:
                odd_count +=1
                # 아이템의 개수가 홀수 개인 아이템이 2개 이상일 경우
                # pesudo-palindromic이 깨지므로 False를 반환한다. 
                if odd_count > 1:
                    return False
        return True

문자열 사용

문자열도 가능하다. 이처럼 PathStorage는 메소드만 올바르게 구현한다면 storage가 어떻든 동작하게 되어있다.

class PathByStringStorage(PathStorage):
    def __init__(self, storage:str = ""):
        self.storage = storage

    def addPath(self,node: TreeNode):
        return PathByStringStorage(self.storage + str(node.val))

    def is_pesudo_palindromic(self) -> bool:
        odd_count = 0
        for item in range(1, 10):
            # count item and check if the number of item is odd
            if self.storage.count(str(item)) % 2 == 1:
                odd_count +=1
                if odd_count > 1:
                    return False
        return True

그러나 문자열이나, 리스트 기반의 PathStorage의 시간복잡도는 is_pesudo_palindromic을 계산할 때, 각item의 개수를 새기 위해 storage의 공간을 전부 탐색해야 하므로 O(len(storage))가 나타나게 된다.

따라서 위의 PathStorage들은 정상적으로 동작하나, 알고리즘 속도가 떨어진다. 따라서 pesudo-palindromic을 잘 표현할 수 있는 다른 storage를 구축해야할 필요가 있다.

BitMask 사용

이번 문제의 포인트는 Node-Value가 1 ~ 9이기 때문에 표현 범위가 매우 좁다. 또한, pesudo-palindromic은 path의 순서는 상관이 없고 각 Node-Value값이 홀수 개인지 짝수 개인지에따라 관련이 있다.

이러한 상황에서 사용할 수 있는 자료구조는 BitMask이다. 컴퓨터의 자료는 이진수로 0 또는 1인 bit로 이루어져 있다. 그리고 자료형태에 따라 bit의 개수가 달라진다.

예를 들어, int형 자료형은 32bit이며, bit를 32개 저장할 수 있다. 만약 5과 2를 하나의 int로 저장하기 위해선 [그림 3]처럼 bit의 위치에 저장하면 된다.

bit의 위치는 비트 연산자인 <<를 사용하면 저장하려는 값에 따라서 고유하게 저장할 수 있다.

그럼 path마다 Node-Value가 홀수 개인지 짝수 개인지 확인은 어떻게 할 수 있을까? 그 방법은 XOR을 이용하면 된다.

XOR은 같은 비트끼리는 0 다른 비트는 1이 나오게 되는 성질을 갖고있다.

XOR은 같은 수끼리 연산하면 0이 나오지만, 한번 더 XOR 연산을 하게되면 [그림 4] 처럼 자기 자신의 수가 나오게 된다. 또한, 이미 저장되어 있는 자료에는 영향을 받지 않으면서도 해당 자료만 영향을 받는다.

마지막으로, 어떻게 pesudo-palindromic을 구현할 수 있을까? 이는 bitmask의 특징을 이용한다. path가 pesudo-palindromic이라면 bit에 단 한개의 1이 저장되어 있거나, 전부 0일 것이다.

path에 - 1을 하게되면 path에 저장되어 있는 1의 하위 비트가 전부 1로 바뀌게 되고, 이를 and 연산하게 되면 [그림 5] 처럼 0이 나타나게 된다. 이는 bit에 단 한개의 1만 있을 때 유효하므로 만일 2개 이상의 수가 홀수개일 경우 0이 나타나지 않는다.

따라서 이를 코드로 옮기면 아래와 같은 자료구조가 완성된다.

class PathByBitStorage(PathStorage):
    def __init__(self, storage:int = 0):
        self.storage = storage

    def addPath(self,node: TreeNode):
        # Node의 Value를 각 bit의 위치에 저장한다.
        # 이미 존재할 경우 XOR을 통해 0으로 초기화 한다.
        # 이를 통해 각 Node.Val이 홀수개인지 짝수개인지 확인할 수 있게 된다.
        return PathByBitStorage(self.storage ^ (1 << node.val))

    def is_pesudo_palindromic(self) -> bool:
        # 만일 숫자가 전부 짝수거나 홀수 개가 1개일 경우 아래의 연산으로 0이 된다.
        return self.storage & (self.storage - 1) == 0

    def show_storage(self) -> None:
        print('storage', self.storage)

예제 소스코드 링크

fromitive github

회고

이번 문제의 핵심은 bitmask를 활용할 수 있는지 확인하는 문제라고 생각한다. Node Value의 표현범위가 크지 않고 bitmask를 통해 이분법(홀수개인지 짝수개인지)으로 나눌 수 있다면 쓸 수 있을 것 같다.

현실 문제에선 활용도가 낮을 것같지만, 발칙하게 떠올린다면 활용할 수 있을거라 기대해본다.

#coding-interview #bitmask #dfs