백준 BOJ 2992 - 크면서 작은 수

깔끔하게 풀어내서 마음에 드는 문제

https://www.acmicpc.net/problem/2992

2992번: 크면서 작은 수

정수X의 자릿수를 쪼개서 어찌저찌 만들어도 되겠다만,

문자열 S에 대해서 '0' ~ '9' 사이의 대소관계는 0~9 사이의 대소관계와 똑같이 계산할 수 있고,

문자열의 길이가 서로 다 같아서 문자열의 길이가 달라지는 경우도 고려 안해줘도 되기때문에

 

X를 정수로 입력받는것이 아니라 문자열 S로 받았고,

문자열 S는 요컨데 char형의 배열이라고 볼 수 도 있기 때문에

char형 배열 S를 정렬해주고

next_permutation 함수를 통해서 구성이 같은 모든 수에 대해

브루트포싱을 진행해줬다.

 

앞선 특성 때문에 단순히 부등호로도 두 문자열을 대소비교할 수 있어서,

소스코드의 길이도 짧아지고 깔끔한 형태로 해결할 수 있었다.

 

고민좀해보면 최솟값이 나왔을때 break 등으로

시간을 아낄수도 있을것같은데

6! = 720 이라 별로 큰 범위도 아니라서

크게 부담없이 해결할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;

int main(){
	string s,k,a="9999999";
	cin>>s;
	
	k=s;
	sort(k.begin(),k.end());
	
	do{
		if(k>s) a=min(a,k);
	}while(next_permutation(k.begin(),k.end()));
	
	if(a=="9999999") cout<<0;
	else cout<<a;
	return 0;
}