[LeetCode] 1718. Construct the Lexicographically Largest Valid Sequence

https://leetcode.com/problems/construct-the-lexicographically-largest-valid-sequence/description/

leetcode - Construct the Lexicographically Largest Valid Sequence

문제 유형: dfs, 재귀, 백트래킹, 비트마스킹

문제 난이도: Medium

 

문제

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이 주어진다.

다음의 규칙을 따르는 수열을 만드시오:

정수 1은 한 번만 나온다.

2~n의 정수는 정확히 두 번 나온다. 그리고 정수 i(2 <= i <= n)가 등장하는 두 인덱스의 차이는 i여야 한다.

가능한 것중에서 사전순으로 가장 큰 것을 반환하시오.

 

풀이

사전순으로 가장 큰 것을 반환해야 하기에, n부터 삽입을 시도한다.

a[index]에 값이 있으면 다음으로 넘기고, a[index]와 a[index+i]에 값을 넣고 상태 숫자에 OR연산으로 추가처리를 한다.

그리고, 재귀호출 후 다시 방문을 제거하여 백트래킹한다.

n부터 넣는 것을 시도하여 최초로 성공적으로 완성된 것이 사전순으로 가장 큰 것이다. 이를 리턴하자.

 

코드

C++

class Solution {
private:
    int n;
    vector<int> ans;
    bool dfs(int index, int state, vector<int>& a) {
        if(index == a.size()) {
            ans = a;
            return true;
        }

        if(a[index] != -1) {
            return dfs(index+1, state, a);
        }

        for(int i = n; i >= 1; --i) {
            if(i == 1 && (state & (1 << i)) == 0) {
                a[index] = 1;
                if(dfs(index+1, state | (1 << i), a)) return true;
                a[index] = -1;
            } else if((state & (1 << i)) == 0 && index + i < a.size() && a[index+i] == -1) {
                a[index] = i;
                a[index+i] = i;
                if(dfs(index+1, state | (1 << i), a)) return true;
                a[index] = -1;
                a[index+i] = -1;
            }
        }
        return false;
    }
public:
    vector<int> constructDistancedSequence(int n) {
        this -> n = n;
        vector<int> arr(2*n-1, -1);
        int state = 0;
        dfs(0, state, arr);
        
        return ans;
    }
};

 

Go

var (
    N int
    ans []int
)

func dfs(index, state int, a []int) bool {
    if index == len(a) {
        ans = a
        return true
    }

    if a[index] != -1 {
        return dfs(index+1, state, a)
    }

    for i := N; i >= 1; i-- {
        if i == 1 && (state & (1 << i)) == 0 {
            a[index] = 1
            if dfs(index+1, state | (1 << i), a) {
                return true
            }
            a[index] = -1
        } else if (state & (1 << i)) == 0 && index+i < len(a) && a[index+i] == -1 {
            a[index] = i
            a[index+i] = i
            if dfs(index+1, state | (1 << i), a) {
                return true;
            }
            a[index] = -1
            a[index+i] = -1
        }
    }
    return false;
}

func constructDistancedSequence(n int) []int {
    N = n
    arr := make([]int, 2*n-1)
    for i := 0; i < len(arr); i++ {
        arr[i] = -1
    }
    dfs(0, 0, arr)
    return ans
}