[S5] 10814. 나이순 정렬

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

10814번: 나이순 정렬

이거. 살짝 당황했다.

문제 이해부터 들어가고 다른 분의 코드 해석도 알려주겠다. 나는 많이 다르게 했다.

 

그러니까 문제를 보면. 나이순으로 정렬은 하되, 먼저 입력된 회원이 먼저 출력이 되어야 한다. 그러니까 같은 나이끼리는 순서가 변경 될 필요가 없다는 것이다.

나는 그래서 정렬을 하는 동시에 만약 왼쪽에 있는 요소와 오른쪽에 있는 요소를 비교할 때, 같은 수가 있다면 왼쪽에 있는 요소가 더 우선순위가 높게, 그러니까 왼쪽에 오도록 하고 싶었다. 

이 방법으로 나는 알고리즘 수업에서 배웠던 병합정렬(merge Sort)를 사용해서 정렬을 하면 어떨까? 라는 생각을 하게 되었다.

내가 하는 말을 이해하기 위해서는 병합정렬에 대한 이해가 필요하다. 병합정렬에 대한 이해가 되었다는 가정하에 설명을 하겠다.

수업에서 과제로 주었던 내용을 가져왔다.

merge하는 과정을 보면 항상, 왼쪽에 있는 배열 부분과 오른쪽에 있는 배열 부분을 비교하여 정렬을 한다. 그러니까 이 과정에 있어서 같을 경우 왼쪽에 있는 요소가 먼저 오도록 할 수 있다는 것이다. 나는 이 개념을 이용해서 정렬을 하였다. 다음 코드를 보면 mergeSort에 대한 내용이 나오게 될 것이다.

#include <cstdio>
#include <iostream>

std::pair<int, std::string> tmp[100000];
void mergeSort(std::pair<int, std::string> a[], int low, int mid, int high) {
    int i = low, j = mid+1;
    int k = 0;
    while (i <= mid && j <= high) {
        if (a[i].first <= a[j].first) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }

    while (i <= mid) tmp[k++] = a[i++];
    while (j <= high) tmp[k++] = a[j++];

    for (int o = 0; o < k; o++) {
        a[low++] = tmp[o];
    }
}

void merge(std::pair<int, std::string> a[], int low, int high) {
    int mid = (low + high) / 2;

    if (low < mid) merge(a, low, mid);
    if (mid < high) merge(a, mid+1, high);

    mergeSort(a, low, mid, high);
}

std::pair<int, std::string> p[100000];
int main(void) {
    int N; 
    std::cin >> N;

    int age;
    std::string name;
    for (int i = 0; i < N; i++) {
        std::cin >> age >> name;
        p[i] = { age, name };
    }

    merge(p, 0, N-1);

    for (int i = 0; i < N; i++) {
        std::cout << p[i].first << " " << p[i].second << '\n';
    }
}

merge부분이 재귀함수를 이용하여 계속 나누는 부분이고, 전부 나누고 나면 mergeSort함수를 호출하여 서로 정렬을 하게 된다. 그 과정에서 같은 요소끼리는 왼쪽에 있는 배열 부분이 더 우선순위가 높다고 보면 된다.

 

자. 지금까지 병합정렬을 이용하여 해결한 코드이다.

이제 다른 방법이 무엇인지 알아보자.

그림으로 보면 다음과 같다.

나이의 크기만큼 vector를 생성해주고, vector안에는 list또는 queue로 구현해준다. 그리고, 입력되는 나이에 맞게 vector에서 list를 찾아 해당 list에 push_back()을 해주어 저장한다. 그러면 출력을 할때 위에서 부터 아래로, 왼쪽에서 오른쪽의 순서대로 출력을 하면 되는 것이다.

코드는 다음과 같다.

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>

int main(void){
    int N; scanf("%d", &N);
    
    std::vector<std::queue<std::string>> v(200);
    int age;
    std::string name;
    while(N--){
        std::cin >> age >> name;
        v[age-1].push(name);
    }
    for(int i = 0; i<200; i++){
        while(!v[i].empty()){
            std::cout << i + 1 << " " << v[i].front() << '\n';
            v[i].pop();
        }
    }
}

당연하게 이 방법이 시간 제한이 적게 나왔다. 참고해야 할 방법이라 생각한다.

 

그리고, 이 문제를 보면 시간 제한이 꽤 나온다.

그래서 fastIo를 사용하였다. 하지만, 풀어야 할 숙제가 하나 생겼다. 나는 queue에 string을 저장해야 한다. char형으로 저장할 수가 없다. 그래서 string으로 입력을 받아야 한다. 그렇다면 readString함수가 필요하다. 다음 코드를 참고하자.

inline void readString(std::string& s){
    char tmp[101];
    char now = read();
    int index = 0;
    while(now <= 32) now = read();
    while(now >= 50) tmp[index++] = now, now = read();
    
    tmp[index] = '\0';
    s = std::string(tmp);
}

inline void writeString(std::string s){
    int isz = 1;
    while(s[isz] != '\0') isz++;
    
    if(isz + widx >= (1<<20)) bflush();
    for(int i = 0; i<isz; i++) wbuf[widx++] = s[i];
    
    write('\n');
}

이 코드를 사용하여 빠르게 입력과 출력을 하게 하였다.

fastIO에 대한 설명은 다음 글을 참고하자.

https://jhcard.tistory.com/78

[C++] 예외..