'2025/02/16'에 해당되는 글 1건

Leetcode Problem:

• Construct the Lexicographically Largest Valid Sequence

Summary

• Given an integer n, find a sequence that satisfies the following conditions: 1 occurs once, each integer between 2 and n occurs twice, and the distance between the two occurrences of each integer is exactly i.

Approach

• The approach is to use a depth-first search (DFS) to try all possible sequences
• We start by initializing a vector to store the sequence and then call the DFS function
• In the DFS function, we try all possible numbers from n to 1, and for each number, we try to insert it into the sequence
• If the number is 1, we insert it at the first position
• If the number is not 1, we try to insert it at the position that is i steps away from the previous occurrence of the number, where i is the number itself
• We use a visited array to keep track of the numbers that have been tried, and we return false if we cannot find a valid sequence.

Complexity

• O(n^2 * 2^n) due to the recursive nature of the DFS function and the fact that we are trying all possible sequences.

Explanation

• The provided solution code uses a depth-first search (DFS) approach to try all possible sequences
• The DFS function is recursive and tries all possible numbers from n to 1
• For each number, it tries to insert it into the sequence
• If the number is 1, it inserts it at the first position
• If the number is not 1, it tries to insert it at the position that is i steps away from the previous occurrence of the number, where i is the number itself
• The solution uses a visited array to keep track of the numbers that have been tried, and it returns false if it cannot find a valid sequence
• The time complexity is O(n^2 * 2^n) due to the recursive nature of the DFS function and the fact that we are trying all possible sequences.

Solution Code:

class Solution {
public:
    int nextIdx(vector& ans){
        for(int i = 0 ; i < ans.size(); i++){
            if(ans[i] == -1)
                return i;
        }
        return -1;
    }
    int visited[21];
    bool dfs(int N, vector& ans){
        bool success = true;
        for(int i = 0 ; i < ans.size(); i++){
            if(ans[i] == -1){
                success = false;
                break;
            }
        }

        if(success){
            return true;
        }
        for(int i = N; i > 0; i--){
            if(visited[i]){
                continue;
            }
            visited[i] = true;
            int idx = nextIdx(ans);
            ans[idx] = i;
            if(i != 1){
                if(idx+i >= (2*N-1)  || ans[idx+i] != -1){
                    ans[idx] = -1;
                    visited[i] = false;
                    continue;
                } else{
                    ans[idx+i] = i;
                }
            }
            if(dfs(N, ans)){
                return true;
            }
            ans[idx] = -1;
            if(i != 1)
                ans[idx+i]= -1;
            visited[i] = false;
                   
        }
        return false;
    }
    vector constructDistancedSequence(int n) {
        vector ans;
        for(int i = 0; i < ((n << 1)-1) ; i++){
            ans.push_back(-1);
        }
        dfs(n, ans);
        return ans;   
    }
};