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

걸린 시간: 2m16s

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

문제 접근 방법

O(nlogn)의 정렬 알고리즘을 사용해야 하지만, 문제 난이도가 쉬운편에 속해서 그냥 내장 sort함수를 사용했다.

C++ 코드

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 n;
8  cin >> n;
9  vector<int> v;
10
11  for(int i=0; i<n; ++i) {
12    int t; cin >> t;
13    v.push_back(t);
14  }
15
16  sort(v.begin(), v.end());
17
18  for(int i=0; i<n; ++i) {
19    cout << v[i] << endl;
20  }
21  return 0;
22}

시간 복잡도

• sort() - O(NlogN)
• 최종 시간 복잡도: O(N logN)

공간 복잡도

• 숫자 카드 N개를 저장 - O(N)
• 최종 공간 복잡도: O(N)