[LeetCode] 1718. Construct the Lexicographically Largest Valid Sequence (Python)

Problem

Solution

backtracking
heuristic (bruteforce)

처음에 한번에 이해하는게 어려웠던 문제.

조건은 아래와 같다.

1 ~ n 까지의 수 중에서

 

1) 1 은 한번만 나옴

2) 2~n 사이의 수는 2번 나옴

3) 사전순으로 정렬했을 때 a[i] == a[j] 에 대해서 |j-i| = n 이어야한다. 예를들어

     arr = [3, 1, 2, 3, 2] 에서 3은 2번 등장하고 두 거리는 3 이다. (arr[0] = 3, arr[3] = 3)

     2는 2번 등장하고 두 거리는 2이다. (arr[2] = 2, arr[4] = 2)

4) 사전순으로 정렬했을 때 가장 큰 배열 return

이때 처음에 숫자를 넣을 때 n (가장 큰 수) 부터 배열에 넣는게 유리하다.

 

 

Code

class Solution:
    def constructDistancedSequence(self, n: int) -> List[int]:
        size = 2*n - 1 # 총 배열 크기
        arr = [0] * size # init arr
        used = [False] * (n + 1) #check used number

        def dfs(idx):
            #arr이 다 채워지면 종료
            if idx == size:
                return True
            #arr가 이미 채워져있으면 다음으로
            if arr[idx] != 0:
                return dfs(idx+1)
            
            #가장 큰 숫자부터 채우기 n~1까지
            for num in range(n, 0, -1):
                #이미 사용한 숫자이면 continue
                if used[num]:
                    continue
                # 1은 한번만 사용
                if num == 1:
                    arr[idx] = 1
                    used[num] = True
                    if dfs(idx + 1):
                        return True
                    #backtracking
                    arr[idx] = 0
                    used[num] = False
                else:
                    #그 외 숫자는 2번 사용
                    if idx + num < size and arr[idx+num] == 0:
                        arr[idx] = arr[idx+num] = num
                        used[num] = True
                        if dfs(idx + 1):
                            return True
                        #backtracking
                        arr[idx] = arr[idx+num] = 0
                        used[num] = False
            #cannot append any num
            return False
        dfs(0)
        return arr

 

Complexity

Time Complexity

최악의 경우 모든 n에대해서 탐색하므로 O(N!) 가 걸리지만

조건에서 n <= 20이라서 20까지는 큰 수부터 체크하므로 무리없이 가능

 

Space Complexity

arr -> O(N)

used -> O(N)

재귀 -> O(N)