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

걸린 시간: 13m55s

문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

접근 방법

나이와 이름을 입력받는다. 그리고 이를 나이순으로 정렬을 해야하며 나이가 같은 경우는 가입한 순으로 정렬해야 한다. 즉 정렬하면서 리스트에 삽입된 순위(?)가 바뀌지 않는 stable sort를 사용해야한다. 하지만 정렬을 하는게 귀찮았기 때문에, map<나이, list<이름>>을 사용해서 정렬을 나이순으로 저절로 되게 하고, 이름은 인접리스트 방식으로 추가하는 방식으로 접근했다.

이렇게 하면 나이순 + 삽입된 순위를 유지하게 된다.

풀이

1#include <bits/stdc++.h>
2using namespace std; 
3#define ios cin.tie(NULL), ios_base::sync_with_stdio(false)
4#define endl '\n'
5
6int main() {
7  int t;
8  cin >> t;
9
10  map<int, list<string> > mymap;
11
12  while(t--) {
13    int age;
14    string name;
15    cin >> age;
16    cin >> name;
17
18    mymap[age].push_back(name);
19  }
20
21  auto it = mymap.begin();
22  while(it != mymap.end()) {
23    auto mylist = it->second;
24    auto it2 = mylist.begin();
25    while(it2 != mylist.end()) {
26      cout << it->first << ' ' << *it2 << endl;
27      ++it2;
28    }
29    ++it;
30  }
31
32  return 0;
33}

시간 복잡도

• map에 데이터 추가: O(logN)
• map순회하며 데이터 출력: O(logN)
  • 각 나이에 속하는 이름 출력: O(M)
• 최종 시간 복잡도: O(M・logN)

공간 복잡도

• 최종 공간 복잡도: O(M・N), M = unique ages, N = number of names