1181 단어 정렬/11650 좌표 정렬하기/11651 좌표 정렬하기2/2750 수 정렬하기/10989 수 정렬하기3/10814 나이순 정렬

1. 1181 단어 정렬

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

1181번: 단어 정렬

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;


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

    int n;
    cin >> n;
    string* arr = new string[n];
    for (int i = 0; i < n; i++) {
        string a;
        cin >> a;
        arr[i] = a;

    }

    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i].size() > arr[j].size()) {
                string temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
            else if (arr[i].length() == arr[j].length()) {
                int idx = 0;

                while (true) {
                    if (arr[i] == arr[j]) {
                        break;
                    }
                    if (arr[i][idx] == arr[j][idx]) {
                        idx++;
                    }
                    else if (arr[i][idx] > arr[j][idx]) {
                        string temp = arr[j];
                        arr[j] = arr[i];
                        arr[i] = temp;
                        break;
                    }
                    else {
                        break;
                    }

                }
            }
        }
    }

    for (int s = 0; s < n; s++) {
        if (s!=0&&arr[s - 1] == arr[s])
            continue;
        cout << arr[s] << "\n";

    }
}

처음에는 위코드로 구현하였다. vs에서 실행했을 때는 성공이었지만 백준에서의 결과는 시간초과였다. 시간복잡도가 O(N^2)이니 당연한 결과였다.

c++ STL의 sort 함수를 바킹독에서 공부하고 돌아왔다.

이후 짠 코드는 아래와 같다.

 

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
bool compare(string a, string b) {
    if (a.length() == b.length())
        return a < b;
    return a.length() < b.length();
}

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

    int n;
    cin >> n;
    string* arr = new string[n];
    for (int i = 0; i < n; i++) {
        string a;
        cin >> a;
        arr[i] = a;

    }

    sort(arr, arr + n, compare);

    for (int s = 0; s < n; s++) {
        if (s != 0 && arr[s - 1] == arr[s])
            continue;
        cout << arr[s] << "\n";

    }

}

결과는 성공!

 

2.11650 좌표 정렬하기

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

11650번: 좌표 정렬하기

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
vector<pair<int, int>>v;

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

    int n;
    cin >> n;
    int x, y;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        v.push_back({ x,y });
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < n; i++) {
        cout << v[i].first << " " << v[i].second << "\n";

    }
    return 0;

}

 

3.11651 좌표 정렬하기2

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

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
vector<pair<int, int>>v;
bool compare(pair<int,int> v1, pair<int,int> v2) {
    if (v1.second == v2.second) {
    return v1.first < v2.first;
    }
    

    return v1.second < v2.second;

}

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

    int n;
    cin >> n;
    int x, y;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        v.push_back({ x,y });
    }
    sort(v.begin(), v.end(),compare);
    for (int i = 0; i < n; i++) {
        cout << v[i].first << " " << v[i].second << "\n";

    }
    return 0;

}

 

4. 수 정렬하기

 

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

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
using namespace std;


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

    int n;
    cin >> n;

    vector<int> v;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        v.push_back(a);
    }
    sort(v.begin(), v.end());

    for (auto v1: v) {
        cout << v1<<"\n";
    }
}

 

5.10989 수 정렬하기 3

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

10989번: 수 정렬하기 3

메모리 초과가 나서 counting sort 알고리즘을 사용해야 했다.

 

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

int arr[10001];

int main() {
    cin.tie(NULL);
    cin.sync_with_stdio(false);
    cout.tie(NULL);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        arr[a] += 1;
    
    }
    for (int i = 1; i < 10001; i++) {
        for (int j = 0; j < arr[i]; j++) {
            cout << i << "\n";
        }
    }
}

 

6.10814 나이순 정렬

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

10814번: 나이순 정렬

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
bool compare(pair<int, string>a1, pair<int, string>a2) {

    return a1.first < a2.first;
}


int main() {
    cin.tie(NULL);
    cin.sync_with_stdio(false);
    cout.tie(NULL);

    int n;
    cin >> n;
    vector<pair<int, string>>v;

    for (int i = 0; i < n; i++) {
        int age;
        string name;
        cin >> age >> name;
        pair<int, string>a = { age,name };
        v.push_back(a);
    }

    stable_sort(v.begin(), v.end(),compare);

    for (int i = 0; i < v.size(); i++) {
        cout << v[i].first << " " << v[i].second << "\n";
    
    }
}

vetor에 넣은 순서를 보존해주기 위해서 stable_sort를 사용해야하는 문제였다.