문제
1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.
사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.
N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.
•
1, 2, 3
•
1, 3, 2
•
2, 1, 3
•
2, 3, 1
•
3, 1, 2
•
3, 2, 1
입력
첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.
출력
첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.
예제 입력 1
4
1 2 3 4
Plain Text
복사
예제 출력 1
1 2 4 3
Plain Text
복사
예제 입력 2
5
5 4 3 2 1
Plain Text
복사
예제 출력 2
-1
Plain Text
복사
My solution
N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.
•
1, 2, 3
•
1, 3, 2
•
2, 1, 3
•
2, 3, 1
•
3, 1, 2
•
3, 2, 1
기존에 사전순으로 순열을 생성하던 방식대로 순열을 생성하면 되겠다.
TC1
4
1 2 3 4
주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.
첫 번째 시도
N은 4이므로 1부터 4까지로 이루어진 순열을 차례대로 생성하다가
주어진 순열을 만났을 때 flag에 true 준다.
이후 호출에서 flag가 true라는 조건에 만족하면 해당 순열을 출력한 다음 이 때 다시 flag를 false로 바꿔주면 될 것 같다.
만약 그 다음에 나타나는 순열이 없다면 DFS를 탈출했을 때까지 flag가 true로 유지될 것이다.
이 경우는 밖에서 -1을 출력한다.
이렇게 풀게 되면 시간 초과가 발생한다.
C++로 풀었는데도 시간초과였기 때문에 알고리즘 자체를 바꾸어야 했다.
N이 10000이기 때문에 모든 순열을 하나하나 구해야하는 테스트케이스에서는 N!의 시간이 걸리기 때문이다.
두 번째 시도
시간복잡도를 낮추기 위해서 next permutation이라는 알고리즘을 사용해야 한다는 것을 알았다.
먼저 오름차순이 끊기는 부분을 찾아 pivot을 업데이트했다. 없다면 다음 순열이 없으므로 -1을 출력했다.
let pivot = -1;
// 맨 뒤에서부터 시작해서 오름차순이 끊기는 부분을 찾는다.
for (let i = givenPerm.length - 1; i > 0; i--) {
if (givenPerm[i - 1] < givenPerm[i]) {
pivot = i - 1;
break;
}
}
// 오름차순이 끊기지 않았으면 다음 순열이 없다.
if (pivot === -1) {
console.log(-1);
return -1;
}
JavaScript
복사
(오름차순이 끊기는 부분을 찾는 이유는 만약 21354가 있다고 하면 45까지 오름차순이고 3을 만났을 때 3 다음의 54는 사전순으로 가장 큰 숫자임을 알 수 있다. 따라서 그보다 앞에 있는(오름차순이 끊기는)3을 바꿔야되기 때문에 이 위치가 pivot이 된다.)
let min = givenPerm[pivot + 1];
let minIdx = pivot + 1;
for (let i = pivot + 2; minIdx < N - 1, i < N; i++) {
const cur = givenPerm[i];
if (givenPerm[pivot] < cur && cur < min) {
min = cur;
minIdx = i;
}
}
JavaScript
복사
(2 2 3 5 1 거꾸로 오름차순이 끊기는 부분을 찾았을 때 인덱스 pivot은 1이다.)
pivot+1은 2(minIdx)이므로 처음에 min은 5이다.
minIdx는 4
이 pivot+2(3)부터 4까지 구간에서
if (givenPerm[pivot] < cur && cur < min) 조건에 따라 min과 midIdx가 업데이트된다.
→ pivot인 값보다는 크면서 가장 작은 값(<min)은 뭔지 찾는다. pivot인 값은 왜 제외하느냐? 나중에 그 위치의 값이랑 바꿔준다.
[givenPerm[pivot], givenPerm[minIdx]] = [givenPerm[minIdx], givenPerm[pivot]];
const answer = [
...givenPerm.slice(0, pivot + 1),
...givenPerm.slice(pivot + 1, N).sort((a, b) => a - b),
].join(' ');
JavaScript
복사
스터디원 풀이
leetcode에 같은 문제
Find the first decreasing index moving from end to start
E.g. [7, 2, 3, 1, 5, 4, 3, 2, 0] num 1 is the first decreasing index going from the end backwards
Swap num 1 with the next large num to its right which is 2
[7, 2, 3, 2, 5, 4, 3, 1, 0]
Reverse/sort nums to the right
[7, 2, 3, 2, 0, 1, 3, 4, 5]
If there is no next permutation reverse the array
오름차순이 끊기지 않으면 최댓값인 것이다.
이전 순열은? 오름차순이 아니라 내림차순이 끊기는지를 확인해서 largeIdx를 찾아 해당 i와 변경한다.
reverse(i + 1);
재귀가 아닌 while문 사용하는 방식
오름차순 깨지는 시점에 다른 숫자와 바꿔야되는 이유?
1, 2, 3
1, 3, 2
처음엔 오름차순이 거꾸로 봤을 때 1개에서 멈춘다.
두번째는 2개에서 멈춘다.
그러니까 그 다음 숫자랑 오름차순에 포함된 숫자들이랑 교환하는 것이 필요하다.
1 3 2 를 보면 1과 3 2 사이의 교환이 일어나야 된다.
3 2 중 가장 작은 값을 찾아가지고 1과 교환하면 된다.
2 3 1
Code
const solution = function (i) {
const [N, givenPerm] = i
.toString()
.trim()
.split('\n')
.map((input, i) => (i === 0 ? +input : input.split(' ').map(Number)));
let pivot = -1;
// 맨 뒤에서부터 시작해서 오름차순이 끊기는 부분을 찾는다.
for (let i = givenPerm.length - 1; i > 0; i--) {
if (givenPerm[i - 1] < givenPerm[i]) {
pivot = i - 1;
break;
}
}
// 오름차순이 끊기지 않았으면 다음 순열이 없다.
if (pivot === -1) {
console.log(-1);
return -1;
}
let min = givenPerm[pivot + 1];
let minIdx = pivot + 1;
for (let i = pivot + 2; minIdx < N - 1, i < N; i++) {
const cur = givenPerm[i];
if (givenPerm[pivot] < cur && cur < min) {
min = cur;
minIdx = i;
}
}
// no Optimization. O(n^2)
// Optimization1. Worst O(nlogn), sort() - 120ms
[givenPerm[pivot], givenPerm[minIdx]] = [givenPerm[minIdx], givenPerm[pivot]];
const answer = [
...givenPerm.slice(0, pivot + 1),
...givenPerm.slice(pivot + 1, N).sort((a, b) => a - b),
].join(' ');
console.log(answer);
return answer;
// Optimization2. O(n), in-place - 152ms
// let K = N - 1;
// let idx = pivot + 1;
// [givenPerm[pivot], givenPerm[minIdx]] = [givenPerm[minIdx], givenPerm[pivot]];
// while (idx < K) {
// [givenPerm[idx], givenPerm[K]] = [givenPerm[K], givenPerm[idx]];
// ++idx;
// --K;
// }
// console.log(givenPerm.join(' '));
// return givenPerm.join(' ');
};
describe('다음순열', () => {
// it('TC1', () => {
// expect(
// solution(`4
// 1 2 3 4`)
// ).toStrictEqual(`1 2 4 3`);
// });
// it('TC2', () => {
// expect(
// solution(`5
// 5 4 3 2 1`)
// ).toStrictEqual(-1);
// });
// it('TC3', () => {
// expect(
// solution(`3
// 2 3 1`)
// ).toStrictEqual('3 1 2');
// });
it('TC4', () => {
expect(
solution(`6
5 1 5 3 2 2`)
).toStrictEqual('5 2 1 2 3 5');
});
});
JavaScript
복사
