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

걸린 시간: 13m55s

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

접근 방법

두 가지 정렬 방식을 한 번에 적용시켜야 하기 때문에 algorithm의 sort함수를 그대로 사용하되, 값을 비교하는 Compare함수를 직접 만들어 길이와 사전순을 동시에 비교하도록 했다.

풀이

1#include <bits/stdc++.h>
2using namespace std;
3
4#define ios cin.tie(NULL), ios_base::sync_with_stdio(false)
5#define endl '\n'
6
7int mycmp(const string &a, const string &b) {
8  const int A = a.length();
9  const int B = b.length();
10  return ((A == B && (a < b)) || (A < B));
11}
12
13int main() {
14  vector<string> v;
15  set<string> myset;
16  int t;
17  cin >> t;
18
19  while(t--) {
20    string s; cin >> s;
21    myset.insert(s);
22  }
23
24  auto it = myset.begin();
25  while(it != myset.end()) {
26    v.push_back(*it);
27    ++it;
28  }
29  
30  sort(v.begin(), v.end(), mycmp);
31
32  const int SIZE = v.size();
33  for(int i=0; i<SIZE; ++i) {
34    cout << v[i] << endl;
35  }
36  return 0;
37}

시간 복잡도

• sort함수 - O(N logN)
  • Compare에서 문자열 길이 구하는 함수 - O(N)
• 최종 시간 복잡도: O(N log(N^2)) 일까 **O(N^2 logN)**일까..?

공간 복잡도

• 최종 공간 복잡도: O(N), N = 단어 개수