문제

BOJ 1620, 나이순 정렬

핵심

• 입력의 크기가 $10^5$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 회원 가입한 사람들의 나이와 이름이 입력으로 주어진다. 회원들은 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬해야 한다. 이 문제를 소개한 이유는 stable_sort라는 개념을 짚고 넘어가기 위해서다. stable_sort는 두 요소가 동등할 때, 정렬 후에도 원래 순서가 유지되는 정렬을 말한다.
• C++에서는 sort함수가 stable sort가 아니며, Java List의 sort함수는 stable sort이다. 해당 사항을 인지하여 구현하도록 하자.

개선

• C++에서 제공하는 sort함수는 stable_sort가 아니므로 회원 가입이 된 순서를 기억해서 나이가 같다면 먼저 회원가입 한 회원을 앞에 오게끔 정렬한다. 하지만 stable_sort를 이용한다면 회원 가입된 순서를 기억할 필요가 없다. 정렬 후에도 기존 순서를 유지하기 때문이다.

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	vector<tuple<int, int, string>> v;
	v.reserve(100'000);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int age;
		string name;
		cin >> age >> name;
		v.push_back({i, age, name});
	}
	sort(v.begin(), v.end(), [](auto& a, auto &b) {
		if (get<1>(a) == get<1>(b))
			return get<0>(a) < get<0>(b);	
		return get<1>(a) < get<1>(b);
	});
	for (int i = 0; i < n; ++i) {
		cout << get<1>(v[i]) << ' ' << get<2>(v[i]) << '\n';
	}
}

코드

시간복잡도

• $O(N\times log_2N)$

C++

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	vector<pair<int, string>> v;
	v.reserve(100'000);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int age;
		string name;
		cin >> age >> name;
		v.push_back({age, name});
	}
	stable_sort(v.begin(), v.end(), [](auto& a, auto &b) {
			return a.first < b.first;
	});
	for (int i = 0; i < n; ++i)
		cout << v[i].first << ' ' << v[i].second << '\n';
}

Java

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static class Person {
        int age;
        String name;
        Person(int age, String name) {
            this.age = age;
            this.name = name;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        ArrayList<Person> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int age = Integer.parseInt(st.nextToken());
            String name = st.nextToken();
            list.add(i, new Person(age, name));
        }
        list.sort((a, b) -> {
            return a.age - b.age;
        });
        for (var e : list)
            bw.write(e.age + " " + e.name + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}