386 - Lexicographical Numbers

info

• 문제 보기: 386 - Lexicographical Numbers
• 소요 시간: 10분 32초
• 풀이 언어: java
• 체감 난이도: 1️⃣~2️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

dfs

풀이 코드

info

• 메모리: 48210 KB
• 시간: 2 ms

class Solution {
    int n;
    List<Integer> ans;

    public void rcs(int i) {
        ans.add(i);
        for (int j = 0; j < 10; ++j) {
            int k = i*10 + j;
            if (k <= n) rcs(k);
        }
    }

    public List<Integer> lexicalOrder(int n) {
        this.n = n;
        ans = new ArrayList<>();
        for (int i = 1; i < 10; ++i)
            if (i <= n) rcs(i);
        return ans;
    }
}

풀이 해설

시간복잡도는 $O(n)$, 공간복잡도는 $O(1)$을 만족하는 방식으로 1 ~ n까지 lex 정렬해야하는 문제이다.

말만 정렬이고, $O(n)$을 만족하기 위해선 수를 순서대로 생성하라는 의도임을 알 수 있다.

메모

• 다시 안풀어봐도 됨
• 운전하느라 피곤했는데 알잘딱 쉬운거 나와주네