문제풀이 유형
순수 logic 짜기
인간 의식의 흐름
예를 들어 1 2 3 4 6 5 를 본다면,
4까지는 멀쩡하다가 6부터 뭔가 흐름이 깨지네?
그리고 6과 5는 내림차순이네?
그러면 4를 이제 5로 바꾸고 뒤에는 4, 6을 순서대로 놔야겠다.
-->
앞에서부터 쭉 읽으면서, 처음으로 ++의 과정이 깨지는 곳(6)을 주시하고,
그 다음에 뒤에서부터 쭉 읽으면서, 처음으로 (뒤에서부터의)오름차순이 깨지는 곳(4)을 본다.
4를 다음 오름차순(5)으로 바꾼 후, 5 뒤를 sort한다.
코드 흐름
앞에서부터 봤을 때 처음으로 ++의 과정이 깨지는 곳은 코드 구현에서는 굳이 체크할 필요 없다.
뒤에서부터 쭉 읽으면서, 처음으로 오름차순이 깨지는 곳(B)을 본다.
B 오른쪽에서, B보다는 크면서 B오른쪽에서 가장 작은 수(다음 오름차순)와 B를 swap한다.
그 뒤 새로운 B의 뒤는 sort한다.
끝에서 처음까지 다 읽었는데도 오름차순이 깨지는 곳이 없다면 마지막 순열인 것이므로 -1을 출력한다.
단 N==1이라면 바로 -1을 출력한다.
코드 오류 원인
logic을 왜곡함.
내가 생각한 인간 의식의 흐름을 코드로 그대로 구현했어야 하는데,
몇 개의 사례로 일반화해서 그 사례에만 맞는 코드를 짬.
사례에 맞는 코드를 짜지 말고, 일반화해서 전체 logic을 생각하기.
전체 코드
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
int N; cin >> N;
vector<int> perm(N);
for (int i = 0; i < N; i++) {
cin >> perm[i];
}
int i = N - 1;
if (i == 0) { cout << "-1"; return 0; } //N==1일 때를 대비
while (perm[i] < perm[i - 1]) { //오름차순이 깨질 때까지 뒤에서부터 읽기
i--;
if (i == 0) { cout << "-1"; return 0; } //모두 읽는다면 마지막 순열이므로 -1 출력
}
int min = max_element(perm.begin()+i, perm.end())- perm.begin(); //다음 오름차순 초기화
int j = i;
for (; j < N; j++) { //B 오른쪽에서 다음 오름차순 찾기: B보다는 크면서, 가장 작은 수
if (perm[i-1] < perm[j] && perm[j] < perm[min]) { min = j; }
}
swap(perm[i - 1], perm[min]); //swap
sort(perm.begin() + i, perm.end()); //B의 오른쪽 sort
for (int i = 0; i < N; i++) {
cout << perm[i] << ' ';
}
return 0;
}코드 수정에 도움되었던 입력과 출력
입력:
3
2 3 1
출력:
3 1 2
입력:
1
1
출력:
-1
입력:
7
1 7 3 2 4 6 5
출력:
1 7 3 2 5 4 6
입력:
7
1 2 3 4 6 5 7
출력:
1 2 3 4 6 7 5
입력:
4
2 1 4 3
출력:
2 3 1 4
