boj 10814 나이순 정렬 c++

boj 10814 나이순 정렬 c++

백준 10814 나이순 정렬 cpp

 

문제 링크 : https://www.acmicpc.net/problem/10814

 

처음에는 버블 정렬로 구현했다가, 시간 초과가 났다.

그래서 퀵 정렬로 구현했는데, 계속해서 터지는 게 문제가 됐다.

이내 퀵 정렬이 stable하지 않는 것이 문제라고 생각해 sort의 맨 마지막 인자로 다음의 compare 함수를 넣었다.

 

bool compare(const pair<int, string>& a, const pair<int, string>& b)
{
    return a.first < b.first;
}

 

그런데 이렇게 해도 내가 만든 테스트케이스는 통과할지언정 서버 채점에서는 계속 틀렸습니다가 떴다.

도저히 답답해서 인터넷을 뒤적이다 stable_sort라는 것을 알게 됐다. 일반적인 sort가 퀵 정렬인 반면 stable_sort의 경우 합병정렬을 기본으로 하기 때문에 안정적으로 정렬할 수 있었다.

그래서 처음에 다음과 같이 코드를 짰는데, 결론적으로는 또 틀렸습니다라는 결과가 나왔다.

 

#include <bits/stdc++.h>
using namespace std;

int testcase_count;
pair<int, string> members[100000];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> testcase_count;
    for (int i = 0; i < testcase_count; i++)
        cin >> members[i].first >> members[i].second;
    stable_sort(members, members + testcase_count);
    for (int k = 0; k < testcase_count; k++)
        cout << members[k].first << " " << members[k].second << '\n';
}

 

왜 틀렸을까 하고 테스트케이스를 넣어보니 이녀석 또한 pair<int, string>을 인자로 넣은 경우 1. int로 정렬, 2. string의 아스키코드 순으로 정렬 하고 있더라.

그래서 여기에 compare함수를 넣었더니 정상적으로 통과할 수 있었다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;

int testcase_count;
pair<int, string> members[100000];

bool compare(const pair<int, string>& a, const pair<int, string>& b)
{
    return a.first < b.first;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> testcase_count;
    for (int i = 0; i < testcase_count; i++)
        cin >> members[i].first >> members[i].second;
    stable_sort(members, members + testcase_count, compare);
    for (int k = 0; k < testcase_count; k++)
        cout << members[k].first << " " << members[k].second << '\n';
}

 

나름 쉬운 문제였음에도 이렇게 오래걸렸다. 머지소트가 unstable하다고 판단한 것에 반성하고, 자료구조를 충분히 공부하지 않았다는 점에 대해서도 반성한다.

 

아래는 내가 시간 초과 결과를 받은 버블정렬 코드

#include <bits/stdc++.h>
using namespace std;

int testcase_count;
pair<int, string> members[100000];

void swap_member(int i, int j)
{
    pair<int, string> temp_member = members[i];
    members[i] = members[j];
    members[j] = temp_member;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> testcase_count;
    for (int i = 0; i < testcase_count; i++)
        cin >> members[i].first >> members[i].second;
    for (int i = testcase_count - 1; i > 0; i--)
    {
        bool swapped = 0;
        for (int j = i - 1; j >= 0; j--)
        {
            if (members[i].first < members[j].first)
            {
                swap_member(i, j);
                swapped = true;
            }
        }
        if (!swapped)
            break;
    }
    for (int k = 0; k < testcase_count; k++)
        cout << members[k].first << " " << members[k].second << '\n';
}

 

refs

• https://withhamit.tistory.com/195

• https://compasstree934.tistory.com/12