LeetCode 386 문제 풀이: 사전 순서 숫자 DFS로 쉽게 해결 (C++, JS, Python)
AI Store에서 AI코딩으로 만들어진 앱을 만나보세요!
지금 바로 방문하기

초보자도 쉽게 이해하는 LeetCode 386: 사전 순서 숫자 문제 해결 가이드 (C++ | JavaScript | Python)

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

알고리즘

대상자

  • 초보 프로그래머 및 인터뷰 준비자
  • O(n) 시간 복잡도와 O(1) 공간 복잡도를 요구하는 알고리즘 문제 해결 기술

핵심 요약

  • DFS 트리 탐색을 활용한 사전 순서 정렬 구현: curr * 10 <= n → 깊이 확장, curr % 10 == 9 또는 curr == n → 백트래킹
  • O(n) 시간 복잡도O(1) 공간 복잡도 달성: 재귀/스택 사용 없이 순수 산술 연산으로 구현
  • 3가지 언어(C++, JavaScript, Python)동일한 로직 구현 예시 제공

섹션별 세부 요약

1. 문제 정의 및 예시

  • 목표: 1부터 n까지의 숫자를 사전 순서로 정렬
  • 예시:

- n = 13[1,10,11,12,13,2,3,4,5,6,7,8,9]

- n = 2[1,2]

  • 문제의 어려움: 문자열 정렬은 O(n log n) 시간 복잡도, 공간 복잡도 증가

2. 알고리즘 설계

  • DFS 트리 탐색 모방:

- 깊이 확장: curr 10 <= ncurr = 10

- 동계 이동: curr + 1 <= ncurr += 1

- 백트래킹: curr % 10 == 9 또는 curr == ncurr /= 10

  • 삼중 조건 분기로 탐색 경로 제어

3. 코드 구현

  • C++:

```cpp

class Solution {

public:

vector lexicalOrder(int n) {

vector ans;

int curr = 1;

while (ans.size() < n) {

ans.push_back(curr);

if (curr 10 <= n) curr = 10;

else {

while (curr % 10 == 9 || curr == n) curr /= 10;

curr++;

}

}

return ans;

}

};

```

  • JavaScript:

```javascript

var lexicalOrder = function(n) {

const ans = [];

let curr = 1;

while (ans.length < n) {

ans.push(curr);

if (curr 10 <= n) curr = 10;

else {

while (curr % 10 === 9 || curr === n) {

curr = Math.floor(curr / 10);

}

curr++;

}

}

return ans;

};

```

  • Python:

```python

class Solution:

def lexicalOrder(self, n: int) -> list[int]:

result = []

curr = 1

while len(result) < n:

result.append(curr)

if curr * 10 <= n:

curr *= 10

else:

while curr % 10 == 9 or curr == n:

curr //= 10

curr += 1

return result

```

4. 복잡도 분석

  • 시간 복잡도: O(n) → 각 숫자가 정확히 한 번만 처리
  • 공간 복잡도: O(1) → 추가 데이터 구조 사용 없음 (결과 배열 제외)

결론

  • DFS 트리 탐색 모방을 통해 O(n) 시간/공간 복잡도를 달성한 알고리즘은 인터뷰 및 알고리즘 문제 풀이에 고효율적
  • 삼중 조건 분기 로직을 통해 재귀/스택 없이도 사전 순서 정렬 가능
  • C++, JavaScript, Python동일한 로직 적용 예시로 언어별 구현 이해 용이