Leetcode 1718. Construct the Lexicographically Largest Valid Sequence

문제

Given an integer n, find a sequence that satisfies all of the following:

The integer 1 occurs once in the sequence.
Each integer between 2 and n occurs twice in the sequence.
For every integer i between 2 and n, the distance between the two occurrences of i is exactly i.
The distance between two numbers on the sequence, a[i] and a[j], is the absolute difference of their indices, |j - i|.

Return the lexicographically largest sequence. It is guaranteed that under the given constraints, there is always a solution.

A sequence a is lexicographically larger than a sequence b (of the same length) if in the first position where a and b differ, sequence a has a number greater than the corresponding number in b. For example, [0,1,9,0] is lexicographically larger than [0,1,5,6] because the first position they differ is at the third number, and 9 is greater than 5.

주어지는 값

• 정수 n이 주어진다.

조건

• n * 2 - 1 크기의 배열을 아래와 같이 채워야 한다.
  • 1은 한번만 등장하고, 2~n의 숫자는 2번씩 등장한다.
  • 1을 제외한 나머지 숫자는 등장하는 간격이 ( index의 차이가 ) 본인의 숫자와 동일해야 한다.
    • EX. [2, x, 2] -> OK , [2, 2] -> X

찾아야 하는것

• 조건을 만족하는 배열중 가장 사전적으로 큰 배열을 리턴하시오

---

예시

n = 3

• [3,1,2,3,2] 이 가장 크다.

---

제한

• $1 <= n <= 20$

---

풀이

• 맨 앞부분 index부터 가장 큰 수로 채워 나간다.
• 이것을 백트래킹으로 구현한다.

class Solution:
    def constructDistancedSequence(self, n: int) -> List[int]:
        size = 2 * n - 1

        ans = [0] * size
        shown = set()

        def backtrack(position: int):

            if position == len(ans):
                return True

            for number in range(n, 0, -1):
                if number in shown:
                    continue

                if number != 1 and (number + position >= len(ans) or ans[number + position] != 0):
                    continue

                shown.add(number)
                ans[position] = number
                if number != 1:
                    ans[position + number] = number

                new_position = position + 1
                while new_position < len(ans) and ans[new_position] != 0:
                    new_position += 1

                if backtrack(new_position):
                    return True

                shown.remove(number)
                ans[position] = 0
                if number != 1:
                    ans[position + number] = 0

        backtrack(0)

        return ans