https://www.acmicpc.net/problem/10972
해당 문제는 순열의 길이를 입력하고 (n) , 1과n으로 이루어진 특정 순열을 입력 시, 다음 순열을 출력하는 프로그램이다.
--다음은 틀린 풀이..--
뭐 내가 앞서, n과m이라는 순열 문제를 풀어보았으니, 그렇게 한번 풀어볼까?
(참고)
https://lee-soo.tistory.com/17
[DFS] 백준 15649번 N과 M (1,2,3) (C++)
https://www.acmicpc.net/problem/15649 이 문제를 풀면서 나에게도 큰 시련이 찾아왔다. 도저히 못풀겠다 사실 글쓴이는 아직 코테 초보수준이라 해본게 브루트 포스랑, dp 랑.. 자료구조 뭐 이런것들인
lee-soo.tistory.com
그냥, 모든 경우의 수를 백트래킹을 통해서 본 후에 그 다음꺼 출력하면 되는거 아니야?
만약에 마지막 경우라면 -1을 출력하고
#include <iostream>
#include <vector>
#include <algorithm>
bool visited[10];
using namespace std;
void task(int n, int depth, int *arr);
vector<int> result;
bool sig = 0;
int main()
{
int n;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++)
cin >> arr[i];
task(n, 0, arr);
}
void task(int n, int depth, int *arr)
{
if (sig == 2)
{
cout << "-1\n";
return;
}
if (sig == 1 && n == depth)
{
for (int i = 0; i < n; i++)
{
cout << result[i] << " ";
}
cout << "\n";
sig = 0;
return;
}
if (sig != 1 && n == depth)
{
for (int i = 0; i < n; i++)
{
if (result[i] != arr[i])
{
return;
}
}
sig = 1;
return;
}
for (int i = arr[0]; i <= n; i++)
{
if (!visited[i])
{
visited[i] = true;
result.push_back(i);
task(n, depth + 1, arr);
result.pop_back();
visited[i] = false;
}
}
}
이 코드는 -1은 구현하지 않고 우선 다음 순열만 출력하는 경우를 고려한 코드인데
시간초과가 걸린다..
생각해보니 앞선 N과 M문제는 8이하의 정수였는데 여기는 10000이하의 정수가 나오니 당연할 따름이지
그렇다면 다른 방식으로 접근을 해야한다!!!
------
순열에 대해 대략적인 파악이 중요하다
사실 이 규칙을 찾는게 처음엔 어려울 수 있다.
예를들어 우리가 1 3 2 5 4 라는 숫자가 있고 이 다음 순열을 구하기 위해선 어떻게 해야할까?
우선 이 다음 순열부터 말하자면 1 3 4 2 5 이다.
왜냐면
뒤에있는 5 4를 크기가 2인 부분 순열로 보자면 이미 순열의 끝부분이다
그렇다면 이제 크기를 3으로 늘려서 2 5 4에 대한 다음 순열을 봐야 한다
이때
2보다 다음으로 큰 수가 맨 앞에온 후, 나머지 숫자에 대해 정렬을 해주면 된다!
EX)
1 3 2 5 4 ->
1 3 4 5 2->
"5 2" 오름차순 정렬
1 3 4 2 5
정답은 이것이다.
즉
오름차순이 끝나는 수 앞 수를 n이라고 할때 이 n과 , 그 이후의 수 중 n보다 다음으로 큰 수를 교환하고
그 이후 정렬을 하면 된다는 것!
이를 코드로 옮겨보자
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n;
int time;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++)
cin >> arr[i];
for (int i = n - 1; i >= 0; i--)
{
if (arr[i] > arr[i - 1])
{
time = i - 1;
break;
}
}
int min_max = time + 1;
for (int i = time + 1; i < n; i++)
{
if (arr[time] < arr[i] && arr[min_max] > arr[i])
min_max = i;
}
if (time == -1)
{
cout << "-1\n";
return 0;
}
int temp;
temp = arr[min_max];
arr[min_max] = arr[time];
arr[time] = temp;
sort(arr + time + 1, arr + n);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << "\n";
}
for (int i = n - 1; i >= 0; i--)
{
if (arr[i] > arr[i - 1])
{
time = i - 1;
break;
}
}
에서 time은 오름차순이 끝나는 순간의 인덱스를 얻으며
for (int i = time + 1; i < n; i++)
{
if (arr[time] < arr[i] && arr[min_max] > arr[i])
min_max = i;
}
해당 조건문을 통해, 비교하려는 수보단 크고, 결정된 수 중에서 작은수가 있으면 그 작은수를 다시 min_max로 옮겨준다
if (time == -1)
{
cout << "-1\n";
return 0;
}
이때 마지막 수라면, 아마 오름차순의 끝이 -1이 될 것이다(인덱스가 i-1인데, i가 0일때까지 갔으니)
그래서 이떄는 -1을 출력하고
이후 사건에 대해서는 바꾼 후 sort를 통해서 답을 출력!
(이전순열)
https://www.acmicpc.net/problem/10974
(모든순열)
n과m 시리즈와 굉장히 유사한 문제
문제를 푸는 방식은 대동소이하니 굳이 설명하진 않겠다~
