[코드포스 Practice13] B. SwapSort

 

그냥 바꾸기만 하면 되나??

되나??

된다.

 

이게 다라고?? 이생각 들어서 두번 읽어봤음

음.. 저거 바꾸는 거 더 좋은 방법이 있을 것 같은데 난 이게 최선이었다. 

 

게다가 시간복잡도 내에 돌아가서 그냥 이 방법대로 짰다. 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
 
int main() {
    int n, m;
    scanf("%d", &n);
    vector <i64> v(n);
    for(int i = 0; i < n; i++)
        scanf("%lld", &v[i]);
 
    int ans = 0;
    vector <ii> vij(n);
    for(int i = 0; i < n - 1; i++)
    {
        int min = v[i + 1];
        int k = i + 1;
        for (int j = i + 1; j < n; j++)
        {
            if (v[j] < min)
            {
                min = v[j];
                k = j;
            }
        }
        if (v[i] > min)
        {
            int tmp = v[i];
            v[i] = v[k];
            v[k] = tmp;
            vij[ans].first = i;
            vij[ans++].second = k;
        }
    }
    printf("%d\n", ans);
    for(int i = 0; i < ans; i++)
    {
        printf("%d %d\n", vij[i].first, vij[i].second);
    }  
    return 0;
}

그냥 맘 편하게 long long으로 짰다. 

 

음.. 난 이렇게 생각하고 짰는데 문제 다시 읽어보니 swap의 횟수가 최소가 아니어도 된다고 했다. 

그럼 그냥 정렬 써도 될 것 같은데..

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
 
int main() {
    int n, m;
    scanf("%d", &n);
    vector <i64> v(n);
    for(int i = 0; i < n; i++)
        scanf("%lld", &v[i]);
 
    int ans = 0;
    vector <ii> vij(n);
    for(int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (v[j] < v[i])
            {
                int tmp = v[i];
                v[i] = v[j];
                v[j] = tmp;
                vij[ans].first = i;
                vij[ans].second = j;
                ans++;
            }
        }
    }
    printf("%d\n", ans);
    for(int i = 0; i < ans; i++)
    {
        printf("%d %d\n", vij[i].first, vij[i].second);
    }  
    return 0;
}

이렇게 짜서 돌려봤는데 에러뜬다.

아.. 이게 이러면 swap 횟수가 n번을 초과하겠구나

음.. 엄...

 

아 좀 더 찾아봤는데 내가 전에 짠 게 선택정렬 비스무리 한 거였다. 

선택정렬은 기준 없이 그냥 최솟값을 찾아서 첫 번째 값과 바꾸는겨

 

선택 정렬 풀었다~~

 

음.. 이제 O(N)에 풀어보려 하는데...

먼저 O(N)이라길래 왕년에 배운 counting sort가 생각났다. 하지만 이건... 배열 인자의 범위가 -10^9 ~ 10^9라 에바..

 

아 O(N)은 아니고 O(logN)

선택정렬에서 min찾는 부분을 O(N)이 아니라 O(logN)으로 줄일 수 있다. 

set을 사용해서!

 

이렇다.

내부적으로 어떻게 생긴지 아니깐 이해하기가 훨 쉬웠음

 

ㅋㅋㅋset 쓸줄 몰라서 결국 북님한테 코드 받았다.

c++ 낯설어