Leetcode 1980. Find Unique Binary String - Python

Leetcode 1980 문제 보기

 

문제 이해하기

각각의 길이가 n인 n개의 이진수 문자열(binary string)들의 리스트인 nums가 있다. (1 <= n <= 16)

중복되는 값의 원소는 존재하지 않을 때, 길이가 n인 이진수 중 nums에 없는 값을 찾아 출력하라.

없는 값이 여러 개 존재한다면 그 중 하나만 출력하면 된다.

 

아이디어 구상

이진수 문자열은 0 아니면 1로 이루어져있다.

따라서 다음과 같은 Decision Tree를 떠올릴 수 있다. (n = 2일 경우를 생각해보자)

By Mesotes

DFS를 이용해 각 Leaf node까지 탐색하면서, binary string을 만들자.

이 때 Leaf node에 도달했을 경우, 만약 binary string가 nums에 존재하지 않는다면 해당 binary string를 return하면 된다.

 

이 때의 시간복잡도는 어떻게 될까?

Decision Tree에서 알 수 있듯이, 최악의 경우 Time Complexity ~ O(2 ^ n)일 것이다.

그러나 nums에 없는 binary string를 발견할 경우, 즉시 return하므로 실제 시간복잡도는 이보다 나을 것으로 생각된다.

 

풀이

DFS 함수를 만들고, 탐색 중에 발견된 값을 return하면 된다.

 

dfs()의 base case는 다음과 같다.

Leaf node에 도달했을 경우, 즉, idx == len(nums) 일 경우 현재까지 만들어진 binary string인 cur를 res로 출력한다.

이 때, res가 nums에 존재한다면 None을 리턴하여 탐색을 지속하도록 하고,

존재하지 않는다면 res를 정답으로 반환하도록 한다.

if idx == len(nums):
    res = cur
    return None if res in nums else res

 

dfs()의 재귀 부분은 다음과 같다.

0과 1에 대해 현재까지 만들어진 binary string을 업데이트하고 DFS탐색을 지속한다.

이 때 res가 None이 아니라면, 즉, nums에 존재하지 않는 값이라면 그 즉시 res를 정답으로 출력하도록 가지치기를 해주자.

for c in "01":
    res = dfs(idx + 1, cur + c)
    if res: return res

 

전체 코드는 다음과 같다.

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        
        def dfs(idx, cur):
            # base case
            if idx == len(nums):
                res = cur
                return None if res in nums else res
            
            for c in "01":
                res = dfs(idx + 1, cur + c)
                if res: return res
            
        return dfs(0, "")

 

---

Leetcode 1980. Find Unique Binary String

https://leetcode.com/problems/find-unique-binary-string/​

​

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다