초보자도 쉽게 이해하는 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 <= n
→ curr = 10
- 동계 이동: curr + 1 <= n
→ curr += 1
- 백트래킹: curr % 10 == 9
또는 curr == n
→ curr /= 10
- 삼중 조건 분기로 탐색 경로 제어
3. 코드 구현
- C++:
```cpp
class Solution {
public:
vector
vector
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의 동일한 로직 적용 예시로 언어별 구현 이해 용이