문제 개요
32비트 양의 정수 n이 주어졌을 때, n에 포함된 자릿수들을 그대로 사용하면서 n보다 값이 큰 수 중에서 가장 작은 32비트 정수를 찾아야 합니다. 만약 조건을 만족하는 수가 존재하지 않는다면 -1을 반환합니다.
예를 들어 입력이 213이라면, 같은 자릿수(2, 1, 3)로 만들 수 있는 수 중 213보다 큰 가장 작은 수는 231이므로 결과는 231이 됩니다.
해결 전략
이 문제는 잘 알려진 "다음 순열(Next Permutation)" 알고리즘을 응용하면 효율적으로 해결할 수 있습니다. 단계별 접근 방법은 다음과 같습니다.
- n을 문자열 s로 변환하고, 문자열 길이를 sz, 성공 여부를 나타내는 플래그 ok를 false로 초기화합니다.
- i를 sz-2부터 0까지 거꾸로 탐색하면서 s[i] < s[i+1]인 지점을 찾습니다. 이 위치가 자릿수를 교환할 기준점입니다.
- 만약 그러한 지점이 없다면(ok가 false라면) 모든 자릿수가 내림차순으로 정렬된 것이므로 더 큰 수를 만들 수 없고, -1을 반환합니다.
- smallest := i, curr := i + 1로 설정한 뒤, j를 i+1부터 sz-1까지 탐색하며 s[j] > s[smallest]이고 s[j] <= s[curr]를 만족하는 j를 찾습니다. 즉, 오른쪽 구간에서 s[i]보다 큰 숫자 중 가장 작은 값을 선택하는 과정입니다.
- s[smallest]와 s[curr]의 자릿수를 서로 교환합니다.
- 교환 후 남은 뒷부분(aux)은 내림차순으로 정렬되어 있으므로, 이를 뒤집으면 오름차순이 되어 해당 구간에서 가장 작은 배치가 됩니다.
- ret은 앞부분(s.substr(0, smallest + 1))과 뒤집은 뒷부분(aux)을 이어 붙인 최종 결과입니다.
- ret이 32비트 양의 정수 범위(INT_MAX = 2147483647)를 초과하면 -1을, 그렇지 않으면 ret을 반환합니다.
C++ 구현 예시
아래 코드를 통해 실제 동작 방식을 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int nextGreaterElement(int n) {
string s = to_string(n);
int sz = s.size();
int i;
bool ok = false;
for(i = sz - 2; i >= 0; i--){
if(s[i] < s[i + 1]) {
ok = true;
break;
}
}
if(!ok) return -1;
int smallest = i;
int curr = i + 1;
for(int j = i + 1; j < sz; j++){
if(s[j] > s[smallest] && s[j] <= s[curr]){
curr = j;
}
}
swap(s[smallest], s[curr]);
string aux = s.substr(smallest + 1);
reverse(aux.begin(), aux.end());
string ret = s.substr(0, smallest + 1) + aux;
return stol(ret) > INT_MAX ? -1 : stol(ret);
}
};
main(){
Solution ob;
cout << (ob.nextGreaterElement(213));
}
입력
213
출력
231
복잡도 분석
시간 복잡도는 자릿수 d에 대해 O(d)이며, 공간 복잡도 역시 O(d)입니다. 32비트 정수는 최대 10자리이므로 사실상 상수 시간 안에 처리할 수 있습니다. 또한 마지막에 stol()로 변환한 값이 INT_MAX를 넘는지만 검사하면 되기 때문에 오버플로우 처리도 간단하게 해결됩니다.