LeetCode - 1718. Construct the Lexicographically Largest Valid Sequence

문제링크

 

문제 설명

정수 n이 주어졌을 때, 다음 조건을 모두 만족하는 수열을 찾습니다.

1. 숫자 1은 수열에서 한 번만 등장합니다.
2. 2부터 n까지의 모든 정수는 수열에서 정확히 두 번씩 등장합니다.
3. 2부터 n까지의 모든 정수 i에 대해, 두 번째 등장 위치와 첫 번째 등장 위치 사이의 거리는 정확히 i가 되어야 합니다.
   • 즉, 숫자 i가 등장하는 두 인덱스 a[i]와 a[j]에 대해, |j - i| = i가 성립해야 합니다.
4. 위 조건을 만족하는 여러 개의 수열 중 사전순으로 가장 큰 수열을 반환해야 합니다.
   • 두 수열 a와 b의 숫자가 처음으로 달라지는 위치에서 a의 숫자가 b의 숫자보다 크다면, a가 더 큰 수열입니다.
   • 예를 들어, [0,1,9,0]은 [0,1,5,6]보다 더 큽니다. (9 > 5)

• 주어진 조건을 만족하는 수열이 항상 존재합니다.

제한 사항

• 1 <= n <= 20

예시

Example 1:

Input: n = 3
Output: [3,1,2,3,2]
Explanation: [2,3,2,1,3] is also a valid sequence, but [3,1,2,3,2] is the lexicographically largest valid sequence.

 

Example 2:

Input: n = 5
Output: [5,3,1,4,3,5,2,4,2]

풀이 흐름

• 사전순으로 주어진 조건에 해당하는 수열을 구하라는 문제 설명을 보고 백트래킹을 떠올렸습니다.
• 반환할 정답 배열의 크기는 2 * n - 1 이므로 정답 배열과 방문 배열을 선언하고 백트래킹으로 정답 배열을 채워나갑니다.
• 이때 사전순으로 가장 큰 수열을 반환해야하므로 n부터 1까지 순차적으로 탐색합니다.
• dfs(int[] ans, boolean[] visit, int n, int idx) 파라미터 설명
  • int[] ans : 정답 배열 입니다.
  • boolean[] visit : 방문 배열 입니다.
  • int n : 문제에서 주어지는 n입니다.
  • int idx : 현재 탐색할 인덱스입니다.
• 만약 idx가 ans의 길이와 같다면 정답 배열을 구했단 뜻이므로 백트래킹을 종료합니다.
• 만약에 ans[idx] > 0 이라면 이미 해당 인덱스에 숫자가 들어있단 뜻이므로 다음 인덱스에 들어갈 숫자를 탐색합니다.
• 위의 2개의 조건에 걸리지 않는다면 n부터 1까지의 숫자 중 현재 인덱스에 들어갈 숫자를 찾습니다.
  • 만약 visit[i]가 true라면 해당 숫자는 이미 사용했단 뜻이므로 건너뜁니다.
  • 만약 사용하지 않은 숫자라면 i가 1 일 때와 2 이상 일 때로 구분해야 합니다. 왜냐하면 1은 한 곳에만 넣으면 되지만 2 이상의 숫자는 두 곳에 넣어야하기 때문입니다.
  • i가 1 일 때
    • ans의 idx 위치에 1을 넣고 visit배열에 1을 사용했다는 표시를 해줍니다.
    • 다음 인덱스에 들어갈 숫자를 탐색합니다.
    • 만약 탐색이 실패하면 ans의 idx 위치의 값을 초기화하고 visit 배열에서도 1을 사용하지 않았다고 변경합니다.
  • i가 2 이상 일 때
    • i가 들어갈 또 다른 인덱스 nidx = idx + i 입니다.
    • nidx에 숫자가 들어있는 숫자가 없는 경우 ans의 idx 위치와 nidx에 i를 넣고 visit배열에 i를 사용했다는 표시를 해줍니다.
    • 다음 인덱스에 들어갈 숫자를 탐색합니다.
    • 만약 탐색이 실패하면 ans의 idx와 nidx 위치의 값을 초기화하고 visit 배열에서도 i를 사용하지 않았다고 변경합니다.

코드

import java.util.*;

class Solution {
    public int[] constructDistancedSequence(int n) {
        int[] ans = new int[2 * n - 1];
        boolean[] visit = new boolean[n + 1];
        dfs(ans, visit, n, 0);
        return ans;
    }

    private boolean dfs(int[] ans, boolean[] visit, int n, int idx) {
        if (idx == ans.length) return true;
        if (ans[idx] > 0) return dfs(ans, visit, n , idx + 1);
        for (int i = n; i >= 1; i--) {
            if (visit[i]) continue;
            if (i == 1) {
                ans[idx] = i;
                visit[i] = true;
                if (dfs(ans, visit, n, idx + 1)) return true;
                ans[idx] = 0;
                visit[i] = false;
            } else {
                int nidx = idx + i;
                if (nidx < ans.length && ans[nidx] == 0) {
                    ans[idx] = i;
                    ans[nidx] = i;
                    visit[i] = true;
                    if (dfs(ans, visit, n, idx + 1)) return true;
                    ans[idx] = 0;
                    ans[nidx] = 0;
                    visit[i] = false;
                }
            }
        }
        return false;
    }
}