[Leetcode] 386. Lexicographical Numbers

문제 요약

• 알고리즘 분류: DFS, 백트래킹
• 난이도: Medium
• 문제내용:
  • n까지 숫자를 사전순으로 정렬 하여라.
• 사이트 주소: https://leetcode.com/problems/lexicographical-numbers/description/

문제풀이 

 이번 문제는 숫자를  사전 순으로 정렬 하는것이다. 1, 2, 3 순이 아니라 1, 10, 100순으로 앞자리가 낮은 순으로 정렬 하는것이다. 이 문제는 깊이 우선 탐색, 백트레킹으로 해결하면된다. 깊이 우선 탐색, 백트레킹 자세한것은 아래 글에서 확인 해보면 된다.

• 백트레킹: https://jih3508.tistory.com/84
• 깊이 우선 탐색: https://jih3508.tistory.com/94

[알고리즘 이론] 깊이 우선 탐색(DFS)

 

문제 접근방법

  0 ~ 9 반복문으로 백트레킹 탐색 하면된다. 구현은 아래 같이 하면된다.

1. 1 ~ 9순으로 dfs 탐색을 한다. 
2. 현재 숫자가 n보다 크면 탐색 종료한다.
3. 1번 경우 아니면 현재 숫자를 리스트에 추가한다.
4. 반복문 0 ~ 9 반복문 i로 돌리다.
5.  현재숫자에서 × 10을 한 뒤 i 더하고 n보다 작으면 다음 백트레킹 탐색 한다.

dfs관련 아래 같이 작성하면 된다.

DFS 코드

Python

def dfs(currentNum):
    # n보다 클경우 현제 숫자 종료
    if currentNum > n:
        return
    result.append(currentNum) # n이하일 경우 추가 한다.
    for i in range(10):
        nextNum = currentNum * 10 + i # 다음수는 10을 곱하고 i를 더한다.
        # 다음 수가 N보다 클경우 종료
        if nextNum > n:
            break
        # n이하일 경우 다음 dfs 탐색
        dfs(nextNum)

Java

public void dfs(int currentNum) {
    if(currentNum > this.n) {
        return;
    }
    this.result.add(currentNum);


    for(int i = 0; i <= 9; i++) {
        int nextNum = currentNum * 10 + i;
        if(nextNum > n) {
            break;
        }

        dfs(nextNum);

    }
}

 

O(n)만큼 시간 복잡도 나온다, 전체 코드는 아래 확인 해보면된다.

 

Code

Python

class Solution:
    def lexicalOrder(self, n: int) -> list[int]:
        result = []
        def dfs(currentNum):
            # n보다 클경우 현제 숫자 종료
            if currentNum > n:
                return
            result.append(currentNum) # n이하일 경우 추가 한다.
            for i in range(10):
                nextNum = currentNum * 10 + i # 다음수는 10을 곱하고 i를 더한다.
                # 다음 수가 N보다 클경우 종료
                if nextNum > n:
                    break
                # n이하일 경우 다음 dfs 탐색
                dfs(nextNum)

        # 1부터 9까지 순서대로 탐색한다.
        for i in range(1, 10):
            dfs(i)

        return result

Java

class Solution {
    List<Integer> result;
	int n;
	
	public List<Integer> lexicalOrder(int n) {
        this.result = new ArrayList<Integer>();
        this.n = n;
        
        for(int i = 1; i <= 9; i++) {
        	dfs(i);
        }
        
        return this.result;
    }
	
	public void dfs(int currentNum) {
		if(currentNum > this.n) {
			return;
		}
		this.result.add(currentNum);
		
		
		for(int i = 0; i <= 9; i++) {
			int nextNum = currentNum * 10 + i;
			if(nextNum > n) {
				break;
			}
			
			dfs(nextNum);
			
		}
	}
}