[C++] 백준 1083번 소트

 

 

이제... 완전 종강이구나...

오늘은 저녁 약속이 있어서 얼른 얼른 끝내야겠다~!!

 

 

무슨 문제를 풀까 고민하다가 골드 문제를 한번 풀어볼까 해서 골라보았다.

 

문제

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

1083번: 소트

 

처음에 2개씩 자리를 서로 바꾸라고 하는 줄 알고 잘못구현했었다...

예제는 잘 나와서 "뭐지?" 했는데

 

다시 보니... 버블 정렬 문제였다 ㅎㅎ

 

// 문제 잘못읽고 구현한 코드

#include <iostream>
using namespace std;

int n, S, temp;
int A[1000001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
	cin >> S;
	
	int j = 0;
	for (int i = 0; i < S; i++) {
		temp = A[j];
		A[j] = A[j + 1];
		A[j + 1] = temp;
		j += 2;
	}
	
	for (int i = 0; i < n; i++) {
		cout << A[i];
		if (i != n - 1) {
			cout << " ";
		}
	}
	
	
	return 0;
}

 

 

 

 

음음... 내가 잘못구현한 코드를 다시 고쳐야겠군..

이라고 했지만....

 

처참....ㅎㅎ

 

 

모르겠어... 왜 틀렸는지 모르겠어요...

 

 

 

아...?? swap이 있었던 것을 까먹고 있었다...

 

결과가 사전 순으로 가장 뒷서도록 하라는 것은 내림차순으로 하라는 뜻이다. 그러니 최대한 앞을 큰 수로 만들어야한다.

이 분의 풀이에 따르면 i번째 자리에서 x칸 떨어져 있는 수는 최소 x번의 swap으로 i번째 자리로 끌어올 수 있다고 한다.

그리고 남은 s번 이내의 swap으로 끌어올 수 있는 가장 큰 수를 찾고 그 수를 현재 위치로 끌어오는 과정을 반복하면 된다고 한다.

#include <iostream>

using namespace std;

int N, S;
int A[51];

int main()
{
    cin >> N;
    for (int i=0; i<N; i++) cin >> A[i];
    cin >> S;
    
    int start = 0;
    while (start < N && S > 0) {
        // S번 이내의 스왑으로 끌어올 수 있는 가장 큰 값을 A[start]로 끌어오기
        int maxIdx = start;
        
        for (int i=start; i<=min(N-1, start+S); i++) {
            if (A[maxIdx] < A[i]) maxIdx = i;
        }
        for (int i=maxIdx; i>start; i--) {
            swap(A[i], A[i-1]);
            S--;
        }
        
        start++;
    }
    
    for (int i=0; i<N; i++) cout << A[i] << " ";

    return 0;
}
출처: https://please-amend.tistory.com/m/161

 

그래서 뭔 소리인가 하고 계속 보고 있었는데....

 

 

(두둥!!)

 

 

어...? 뭔가 나... 또 문제를 잘못 이해한 것 같은데...???

가장 큰 수를 찾고 그 수를 현재 위치로 끌어오는 거라고...??

흠... 잠시만 다른 풀이도 보고 와야겠다...

 

#include <iostream>
#include <algorithm>

using namespace std;

int N,S,temp, cnt = 0, maxnum,maxidx;
int arr[51];

int main (){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> arr[i];
    }
    cin >> S;

    for(int i = 0; i < N - 1 && S != 0; i++){
        cnt = 0;
        maxnum = arr[i];
        maxidx = i;
        for(int j = i + 1; j < N && cnt < S;j++,cnt++){
            if(maxnum < arr[j]){
                maxnum = arr[j];
                maxidx = j;
            }
        }
        int j = maxidx;
        if(maxidx > i){
            while(j != i){
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                j-- ;
            }
        }
        S -= (maxidx - i);
    }   
    for(int i = 0; i < N; i++){
        cout << arr[i] << " ";
    }
    return (0);
}
출처: https://allmymight.tistory.com/109

 

아!!!!!! 이제야 처음에 찾은 풀이가 무슨 뜻인지 알겠다...

 

일단... 내가 문제를 또 잘못 이해한 것이 맞았다. 사전 순으로 가장 뒷서는 것 즉, 가장 큰 숫자를 최대한 앞으로 당겨와야한다는 의미라고 한다. 난 그냥 2개씩 비교하여 큰 것을 앞으로 가져오라는 건줄...

 

그리고 가장 큰 수의 인덱스에서 현재 위치가 될 때까지 1을 감소시켜가며 swap을 해주면 되는 것이다. 그러면 가장 큰 수는 현재 위치로 이동할 수 있다. (아까 앞에서 한 말이 이런 뜻이였구나)

 

이 분도 말씀하시기를...

아무리 앞에 있는 것을 먼저 바꿔도 뒤에 있는 것 하나를 가져오는 것이 사전 순으로는 뒤에 있는 것이라고 한다.

 

ㅠㅠ 문제를 이해하기도 힘들다...

아직 나는 많이 부족한 것 같다...

 

 

계속 열심히 하자~!!!!!