[백준/C++] 16943 숫자재배치

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

4월 5월은 항상 결혼식이 많다. 최근에 사회도 봤다. 돈이 없다. 힘들다. 그래서 문제 풀기와 블로그 글 작성에 시간을 쏟지 못했지만, 틈틈히 nest도 공부하고 있고 클론 코딩을 하면서 익숙해지려는 중입니다..

어쨌든, 쉬울줄 알았는데 생각보다 문제를 잘못 풀고 있어서 회고를 해봅니다.

 

문제를 해결함에 있어서, 그리고 현재 개발일을 하면서 생각치도 못한 조건이 발견된다면 그것은 곧 버그로 이어지더라고요. 그래서 알고리즘 문제를 풀면서 다양한 조건들을 파악해 버그를 미리 예방하는 것이 좋습니다. 그러한 사고를 이끄는 것이 알고리즘 문제 해결이 아닐까 싶습니다. 그래서 대부분의 기업들이 코딩테스트를 치루는 것 같습니다.

이 문제는 숫자의 범위를 제대로 파악하지 못한 원인이 큰 문제였습니다. n이 10^9인데 만약 10,000,000과 99,999,999 사이에서 가장 큰 숫자를 구한다고 한다면 당연히 10,000,000이 답이 되겠지만?

컴퓨터는 그런거 모르잖아요? 그래서 for문으로 다 돌려서 확인하자~ 하면 뭐 얼마나 걸리겠어 했는데, 89,999,999번을 돌려하는 대참사가 발생하고, 제가 푸는 방식은 memcpy를 계속 돌려서 당연히 시간초과가 발생하게 되는 것이었습니다.

그리고 next_permutation으로 문제 해결을 많이 해왔는데, 시간복잡도를 생각안했더라고요. 그래서 당연히 조합이니까 안될줄 알았는데, 되더라고요 정렬을 시켜둔 상태에서는 O(n)의 시간복잡도가 나옵니다.

이런 빈틈있는 부분도 고쳐야하는 부분중에 하나가 될 것입니다. 어쨌든..

첫번째 조건은 A의 길이가 B보다 길때 어떠한 방법을 사용해도? 그리고 0이 앞으로 나왔을때 가능할 수 있지만, 해당 문제는 숫자를 원했으니 0이 앞에 들어간것을 숫자로 취급하지 않겠죠? 그래서 바로 -1을 리턴합니다.

두번째 조건은 A의 길이가 B보다 짧을때 입니다. 그렇다면 미리 저장해둔 aNumber배열에서 제일 큰 값부터 차례대로 출력한다면 당연히 제일 큰 값이 나오게 되겠죠?

세번째 조건은 A의 길이와 B의 길이가 같다면? 입니다. 이때는 next_permutation을 통해서 전체 순열을 살펴봅니다. 그리고 이 문제는 0이 앞으로 오는것을 원치않기때문에 continue를 걸어두고, 해당 숫자가 B보다 작고, answer가 num보다 작다면? answer를 num으로 바꿔줍니다. 이때, answer를 0으로 정의해둔다면? 당연히 틀린 문제가 됩니다.

왜냐하면 우리는 0을 숫자라고 부르지 않기로 했으니까요? 예시로 0과 9를 입력하면 답이 0이 나오게 됩니다. 그리하여 answer를 -1로 초기화해 문제를 해결할 수 있습니다.

아래는 정답 코드입니다.

#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;

string A,B;
int aNumber[11], bNumber[11];

int main() {
	
	cin >> A >> B;
	
	for(int i = 0; i < A.length(); i++){
		int a = A[i] - '0';
		aNumber[a]++;
	}
	
	if(A.length() > B.length()) {
		cout << -1;
		return 0;
	} else if(A.length() == B.length()){
		
		long long answer = -1;
		sort(A.begin(), A.end());
		
		int a = stoi(A); int b = stoi(B);
		
		do{
			cout << "A : " << A << "\n";
			int num = stoi(A);
			if(A[0] == '0') continue;
			if(num < stoi(B) && answer < num){
				answer = num;
			}
			
		}while(next_permutation(A.begin(), A.end()));
		
		cout << answer;
		
	} else if(A.length() < B.length()){
		long long answer = 0;
		for(int i = 9; i >= 0; i--){
			for(int j = 0; j < aNumber[i]; j++){
				answer += i;
				answer *= 10;
			}
		}
		
		cout << answer / 10;
	}
	
	
	
	return 0;
}