[코테연습] 386. Lexicographical Numbers

- DFS/트리 문제

 

https://leetcode.com/problems/lexicographical-numbers/description/?envType=daily-question&envId=2024-09-21

 

- 문제분석

1. 1..n 까지의 숫자가 있을때, 사전순서대로 정렬하여 리턴하라.

2. 1, 10, 11, 12, 13,...

 

- 문제 풀이

1. String 으로 변환하여 정렬하여 문제를 해결할 수 있다.

 

class Solution {
    public List<Integer> lexicalOrder(int n) {

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i+1);
        }
        Collections.sort(list, (o1, o2)-> {
            String a = String.valueOf(o1);
            String b = String.valueOf(o2);
            return a.compareTo(b);
        });

        return list;
    }
}

 

2. DFS 를 이용하여 숫자 증감을 통해 구현한다.

 

class Solution {
    public List<Integer> lexicalOrder(int n) {
        
        List<Integer> list = new ArrayList<>();

        int current = 1;
        for (int i = 1; i <= n; i++) {
            list.add(current);

            //현재 숫자 * 10 이 n 이하인지 확인한다.
            if (current * 10 <= n) {
                //n 이하라면, current * 10 을 한다.
                current = current * 10;
            } else {
                // current 1의 자리가 9 이거나 current 가 n 보다 크다면, current 를 10으로 나눈다.
                // 9 => 0, 19 => 9, 
                while ( current % 10 == 9 || current >= n) {
                    current = current / 10;
                }
                current+=1;
            }
        }

        return list;
    }
}