#11650번 좌표 정렬하기 (c++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    vector <pair<int,int>> v;
    
    for(int i=0; i<T; i++){
        int a,b = 0;
        cin >> a >> b;
        v.push_back(pair<int,int>(a,b));}
        
    sort(v.begin(),v.end());
    
    for(int i=0; i<T; i++){
        cout << v[i].first << " " << v[i].second << "\n";}
    
    return 0;
 }

Vector의 pair를 사용하여 쉽게 풀렸다. 

Vector와 Sort의 연계는 문제를 푸는데 있어서 꿀조합인것 같다. 

Sort 한 줄 만으로 pair의 모든 요소들을 비교해주기 때문이다. 

 

처음에는 vector의 pair가 아닌 선택정렬로 사용해서 풀었는데, 

모든 테케는 통과했지만 시간초과가 떠버렸다. 

문제에서 입력 값의 갯수가 100,000개까지 가능하다했으니, 시간초과가 나오는건 당연할법도 했다. 

#include <iostream>
using namespace std;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    int arr[T][2];
    
    for(int i=0; i<T; i++){
        for(int j=0; j<2; j++){
            cin >> arr[i][j];
        }
    }
    for(int i=0; i<T-1; i++){
        for(int j=i+1; j<T; j++){
            if(arr[i][0]>arr[j][0]){
                swap(arr[i][0],arr[j][0]);
                swap(arr[i][1],arr[j][1]);
            }
            else if(arr[i][0]==arr[j][0]){
                if(arr[i][1]>arr[j][1]){
                    swap(arr[i][0],arr[j][0]);
                    swap(arr[i][1],arr[j][1]);
                }
            }
        }
    }
    for(int i=0; i<T; i++){
        for(int j=0; j<2; j++)
            cout << arr[i][j] << " ";
        cout << "\n";
    }
    
    return 0;
}

딱 봐도 선택정렬로 푼 문제는 Vector + Pair, 그리고 Sort의 조합으로 푼 맨 위의 코드보다도 복잡해 보인다. 

 

이런 의미에서 Vector && Pair && Sort는 정말로 꿀조합이지만,

그냥 가져다가 써서 맞추는데 그치지 말고 해당 STL의 내부 구조까지 파악할 수 있어야 한다. 

 

해당 내부 구조를 내가 직접 구현할 수 있도록 공부를 해봐야지

다른 정렬들과의 차이점을 정확히 파악하고  

개발자스러운 효율적인 코드를 작성할 수 있을테니 말이다. 

 

보다 열심히 공부하고 싶다.