정렬 문제들

cpp에서의 정렬

다른 언어들과 비슷하게 std::algorithm 안에 sort라는 아주 강력한 정렬함수가 내장되어 있지만, 이것만 가지고는 못푸는 문제들이 진짜 많다.

counting sort

문제
다른 정렬문제에 비해 유난히 정답률이 낮다... 아마 통상적으로 counting을 풀면 timeout이 나오기 때문인거같다.

원리는 다른글에서 다루도록 하고 여기서는 코드랑 풀이법만 적어보자면,

#include <iostream>

#define MAX_NUM 10001
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;
    int arr[n], ans_arr[n];
    int counter = 0;
    int count[MAX_NUM] = {0};

    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        arr[i] = val;
    }
    
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }
    for (int i = 1; i <= MAX_NUM + 1; i++) {
        count[i] += count[i-1];
    }

    for (int i = 0; i < n; i++) {
        ans_arr[count[arr[i]]- 1] = arr[i];
        count[arr[i]]--;
    }
    
    for (int i = 0; i < n; i++) {
        cout << ans_arr[i] << "\n";
    }
}

말 그대로 counting sort를 구현해서 풀면된다.

하지만 이 counting sort의 진가는 다음 문제에 있다.

통계학

링크
문제만 보면 이게 왜 정답률이 언더 30%일까 싶지만, 최빈값 때문이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;
#define MAX_NUM = 8001

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n;
    int avg, mid, most, range;
    cin >> n;

    vector<int> vec;

    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        vec.push_back(val);
    }

    int arr[n], ans_arr[n];
    int counter = 0;
    int count[MAX_NUM] = {0};

    for (int i = 0; i < n; i++) {
        arr[i] = vec[i];
    }
    
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }
    for (int i = 1; i <= MAX_NUM + 1; i++) {
        count[i] += count[i-1];
    }

    for (int i = 0; i < n; i++) {
        ans_arr[count[arr[i]]- 1] = arr[i];
        count[arr[i]]--;
    }


    sort(vec.begin(), vec.end());

    avg = static_cast<int>(accumulate(vec.begin(), vec.end(), 0) / n);
    mid = vec[static_cast<int> (n/2)];
    most = 최빈값 구하기 
    range = vec.back() - vec.front();
    
    cout << avg <<"\n";
    cout << mid <<"\n";
    cout << most <<"\n";
    cout << range <<"\n";
}

정말 놀랍게도, 최빈값을 구하는 내장함수가 없다! R이나 matlab에는 있을거같긴한데 아무튼 cpp에는 없다. 그래서 이 최빈값을 구하려면 counting sort를 이용해야한다. counting sort는 각 원소의 등장횟수를 counting 해서 그중 가장 큰 값의 idx가 최빈값이 되는 방식이다.

하지만 이 문제에서 함정은 수가 양수만 있는게 아니라 음수도 있다는점이다. 따라서 counting sort를 받는 배열을 *2 + 1 해서 준비해야하고, 0이 arr.size() / 2 위치에 가도록 한 다음 각 수의 숫자를 세야한다.

이중정렬

조건 A와 조건 B가 존재하고, 그 조건에 맞춰서 순서대로 정렬을 하는 문제이다.

예를 들어 x좌표가 작은 순, 만약 똑같다면 y좌표순 이런 문제들이다.

11650

링크

위에서 말한 좌표문제이다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class point {
    public:
    int x;
    int y;

    point(int _x, int _y) {
        x = _x;
        y = _y;
    }
};

bool coord_comp(point &a, point &b) {
    if (a.x < b.x) {
        return true;
    } else if (a.x == b.x) {
        if (a.y < b.y) {
            return true;
        } else return false;
    } else return false;
}

int main() {
    int n;
    cin >> n;
    int x, y = 0;
    vector<point> vec;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        vec.push_back(point(x, y));
    }

    sort(vec.begin(), vec.end(), coord_comp);
    for (int i = 0; i < n; i++) {
        cout << vec[i].x << " " << vec[i].y << "\n";
    }
}

이러한 문제들은, 값을 class 혹은 구조체로 받아서 풀면 된다.

point x, y를 받는 x, y class를 이용하여 값을 받고 vector에 저장한다.
그리고 bool compare함수를 만들어서 sort가 참고할 sorting 규칙을 만들어주면 된다.

bool coord_comp(point &a, point &b) {
    if (a.x < b.x) {
        return true;
    } else if (a.x == b.x) {
        if (a.y < b.y) {
            return true;
        } else return false;
    } else return false;
}

비교할 a와 b 중 a.x < b.x 라면, true를 반환하여 두 수간의 변경이 이루어지도록 한다.

만약 두 수의 값이 같다면, y를 같은 방식으로 비교한다. 그 밖의 경우는 전부 false를 반환, 교환이 이루어지지 않도록 한다.

이 밖에도, 나이순 정렬, 문자열 길이순 정렬 등 다양한 문제들이 있는데 하나만 알면 나머지도 비슷하게 풀 수 있다.

좌표 압축

문제이해가 좀 어려운 문제였다. 처음에는 그냥 제일 큰 좌표부터 그 다음 좌표는 1 그 다음은 2 이런식으로 푸는건줄 알고

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>

using namespace std;

int main() {
    int n, temp;
    cin >> n;
    vector<int> vec;
    vector<int> sorted;
    vector<int> vec2;

    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        vec.push_back(val);
        sorted.push_back(val);
    }
    sort(vec.begin(), vec.end());

    for (int i = 0; i < n; i++) {
        if (temp != vec[i]) {
            temp = vec[i];
            vec2.push_back(vec[i]);
        }
    }
    vec.clear();

    for (int i = 0; i < n; i++) { 
        int dis;
        dis = find(vec2.begin(),vec2.end(), sorted[i]) - vec2.begin();
        vec.push_back(dis);
    }

    for (int elem : vec) {
        cout << elem << " ";
    }
}

이런 미친 for문 코드를 작성했다. 물론 이 코드도 erase unique를 쓰면 더 빨라지기는 한다.

아무튼 이런 문제가 아니였다.

좌표압축

링크
배열 안의 원소 elem 보다 작은 원소의 갯수가 해당 좌표의 압축값이 된다는 문제이다.

따라서 2 4 -10 4 -9 같은 경우 2 3 0 3 1이 되는것이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> vec;
    vector<int> sorted;
    vector<int> vec2;

    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        vec.push_back(val);
        sorted.push_back(val);
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    for(int i = 0; i < n; i++) {
        int ans = lower_bound(vec.begin(), vec.end(), sorted[i]) - vec.begin();
        cout << ans << " ";
    }
}

이 문제의 풀이순서는 다음과 같다.

1. 두 개의 vector에 값을 입력받는다. (하나는 원본보존용, 하나는 정렬용)

2. 하나의 vector를 정렬한다.

3. 중복값을 전부 제거한다.

4. 원본을 loop돌면서 정렬된 vector에서 idx를 가지고 온다.

여기서 중복값 제거를 위해서 사용하는 함수가 erase와 unique이다.

unique

유니크 함수는 지정된 vecotr 범위내에서 중복되는 값들을 전부 맨 뒤 쓰레기값으로 보내고, 해당 쓰레기값이 시작되는 위치를 반환한다.

erase

erase는 범위내의 값들을 지우는 역할을 한다.

따라서 이 둘을 조합해서 쓰면 쓰레기 값의 시작점부터 끝까지 전부 지울 수 있는것이다.

그리고 idx를 가지고 오는 과정은 for문을 통해서도 구현이 가능하지만 내장함수 lower_bound역시 가능하다.

lower_bound

이 함수는 범위내의 vector 값들과, src 백터값을 비교하여 src에서 해당 elem이 있다면 가장 작은 idx를 가지고오는 역할을 한다.

이러한 과정을 거치면 위에서 말한 4단계를 완수할 수 있다.