처음 시도했던 접근 방법은 이렇다. 일단, 두 수를 비교했을 때 어떤 수가 앞에 와야 하는지 생각해봤다.
1. 맨 앞자리수가 커야 한다. 예를 들어서, 18과 2를 비교했을 때 만들 수 있는 조합은 182와 218인데 218이 더 큰 것을 보면 앞 자릿수가 커야 조합했을 때 큰 수 를 만들 수 있다.
2. 앞자리수가 같다면 마찬가지 논리로 뒷자리 수가 커야 한다. 예를 들어서, 28과 27을 비교했을 때 만들 수 있는 조합은 2827과 2728인데 2827이 더 큰 것을 보면 알 수 있다.
3. 모든 자리의 숫자가 같지만 자릿수가 다르다면, 자릿수가 같을 때까지 맨 앞의 수를 넣은 후 비교한다. 예를 들어서 382와 38을 비교했을 때, 382와 (38에 맨 앞 자릿수인 3을 붙인 383을 비교한다. 그렇게 하면 38382가 만들어지는데 이것은 다른 조합인 38238보다 더 큰 것을 알 수 있다.
4. 이렇게 해서도 모두 같으면 더 작은 수가 더 큰 조합을 만들 수 있다. 예를 들어서, 383과 38을 비교했을 때 만들 수 있는 조합은 38383과 38338인데 38383이 더 큰 것을 보면 수가 더 적은 38이 앞에 있는 상황인 것을 알 수 있다.
// reference를 불러와서 실제 배열에도 swap의 결과를 반영한다.
void swap(int& a, int& b){
int tmp=a;
a=b;
b=tmp;
}
void qsort(vector<int>& arr, int start, int end){
// 분할된 원소가 0개이거나 1개일때까지 함수 호출
// start+1==end일 때, 원소의 개수는 1개
if(start+1>=end) return;
int pivot=start;
// 값 설정 기준 : 첫번째 원소
int bigger=start+1;
// bigger : pivot보다 큰 원소를 찾는 index
// 값 설정 기준 : pivot + 1
int smaller=end-1;
// smaller : pivot보다 작은 원소를 찾는 index
// 값 설정 기준 : 마지막원소
// `bigger`와 `smaller`이 교차할때 까지 pivot보다 크거나 작은 원소들을 서로 교환한다.
while(bigger<=smaller){
// end는 아무 원소도 가리키지 않으므로 end보다 작아야한다.
// bigger이 가리키는 원소가 pivot이 가리키는 원소보다 작으면 계속 bigger을 키운다.
while(bigger<end && arr[bigger]<=arr[pivot]) ++bigger;
// smaller은 나중에 pivot과 swap해야하기 때문에 pivot의 index인 start와 같으면 안된다.
// 역시, smaller이 가리키는 원소가 pivot이 가리키는 원소보다 크면 계속 smaller을 줄인다.
while(start<smaller && arr[pivot]<=arr[smaller]) --smaller;
// bigger과 smaller이 교차하면 종료한다.
if(bigger>=smaller) break;
// 교차하지 않았다면 서로가 가리키는 원소를 swap하고 다시 반복한다.
swap(arr[bigger], arr[smaller]);
}
// 교차했다면 pivot과 smaller가 가리키는 원소를 서로 교환한다.
// 이렇게 하면 pivot 왼쪽에는 pivot보다 작은것, 오른쪽에는 pivot보다 큰것이 위치한다.
swap(arr[smaller], arr[pivot]);
// pivot을 기준으로 오른쪽과 왼쪽으로 나눠서 다시 정렬을 수행한다.
qsort(arr, smaller+1, end);
qsort(arr, start, smaller);
}
