Machineboy空
입력값과 같은 구성의 수 중 가장 작은 큰 수: NextPermutation 본문
내일 풀 수학 문제의 개수는 오늘 푼 문제 개수의 수와 숫자의 구성이 같으면서, 오늘 푼 문제 개수의 수보다 큰 수 중 가장 작은 수입니다.
예를 들어, 오늘 67문제를 풀었으면 다음 날 76문제를 풉니다. 오늘 푼 문제의 개수를 줬을 때 다음날 풀 문제의 개수를 출력하는 프로그램을 작성하세요.
입력
오늘 푼 문제의 개수 자연수 N
1<= N <= 999999
출력
다음날 풀 문제의 개수 출력
문제요약
입력값과 같은 구성의 수 중 가장 작은 큰 수
풀이 포인트
- Next-permutation
- 정렬
REVIEW
경우의 수가 다양해지면 자꾸 생각하길 포기한다.
작은 단계로 나누어 생각하는 법을 또 명심!
999999까지가 아닌 1000까지만 해서 생각해보고 넓히고 하면 됌!
CODE
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int nextProblemCount(int todayCount) {
string todayStr = to_string(todayCount);
bool hasNext = next_permutation(todayStr.begin(), todayStr.end());
if (hasNext) {
return stoi(todayStr);
}
return -1;
}
int main() {
int todayCount;
cin >> todayCount;
int nextCount = nextProblemCount(todayCount);
if (nextCount != -1) {
cout << nextCount << endl;
} else {
}
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int nextProblemCount(int todayCount) {
string todayStr = to_string(todayCount);
int n = todayStr.length();
// 1. 뒤에서부터 감소하는 부분 찾기
int i = n - 2;
while (i >= 0 && todayStr[i] >= todayStr[i + 1]) {
i--;
}
// 모든 수가 내림차순이면 다음 순열이 없으므로 -1 반환
if (i == -1) {
return -1;
}
// 2. 감소하는 부분의 오른쪽에서 가장 작은 숫자 찾기
int j = n - 1;
while (todayStr[j] <= todayStr[i]) {
j--;
}
// 3. 숫자 교체
swap(todayStr[i], todayStr[j]);
// 4. 교체한 숫자 오른쪽 부분을 오름차순으로 정렬
reverse(todayStr.begin() + i + 1, todayStr.end());
return stoi(todayStr);
}
int main() {
int todayCount;
cin >> todayCount;
int nextCount = nextProblemCount(todayCount);
if (nextCount != -1) {
cout << nextCount << endl;
} else {
cout << "No next permutation" << endl;
}
return 0;
}
'Computer > Coding Test' 카테고리의 다른 글
1717: 집합의 표현 - Union-Find Tree (0) | 2024.07.22 |
---|---|
15649: N과 M(1) - 백트래킹 (2) | 2024.07.22 |
1813: 논리학 교수 - Ad Hoc (0) | 2024.07.02 |
프로그래머스 PCCP 역량인증 시험 후기와 반성 (0) | 2024.06.16 |
14469: 소가 길을 건너간 이유 3 - 그리디 (1) | 2024.06.09 |