[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다.
문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.
Q 5.11 다음 순열 구하기
n개의 원소로 만들 수 있는 순열의 갯수는 n!개이다. 순열을 사전 순으로 정렬할때 다음으로 올 순열을 구하라.
ex) P=<1,0,3,2>의 다음 순열은 <1,2,0,3>
순열이 사전 순으로 정렬되어 있으므로, 순열의 크기를 조금만 증가시키는 것이 핵심이다.
배열 A = <6,2,1,5,4,3,0> 이라고 할때 A의 접미사 중에서 가장 긴 감소 순열은 <5,4,3,0> 이다.
해당 순열은 사전 순으로 감소일때 다음순열이 존재하지않는다.
따라서 5의 앞의 1과 감소순열 안에서 가장 작으며, 앞의 1보다 큰수와 교환을 하게 되면
다음 순열인 <6,2,3,5,4,1,0>이 된다.
해당 내용의 코드와 결과는 다음과 같다.
'C++ 학습 > C++ 코딩인터뷰[5장]' 카테고리의 다른 글
| [5. 배열] 5.13 온라인 데이터 샘플 구하기 (0) | 2025.01.15 |
|---|---|
| [5. 배열] 5.12 오프라인 데이터 샘플 구하기 (0) | 2025.01.15 |
| [5. 배열] 5.10 배열 안의 원소로 순열 구하기 (0) | 2025.01.15 |
| [5. 배열] 5.9 n보다 작은 모든 소수 나열하기 (0) | 2025.01.14 |
| [5. 배열] 5.8 대체 연산 (0) | 2025.01.14 |
