백준 링크 : https://www.acmicpc.net/problem/2751

문제 개요

N개의 수가 주어졌을 때 오름차순으로 정렬한다.

아이디어

• 입력이 1,000,000까지 들어오지만 sort함수는 평균 시간 복잡도가 $n \log n$인 것을 떠올리며, sort함수로 해결해 본다.

주의사항

• 최대 입력이 1,000,000임을 상기해야 한다.
  • , 버블 정렬, 선택 정렬, 삽입 정렬 $O(n^2)$의 시간복잡도를 가지고 있으며, 이 방법으로는 최대값을 통과할 수 없다는 것을 알아야한다.

코드

// 아래의 코드는 dev c++환경에서 동작됩니다.
// visual studio에서는 bit/stdc++.h가 기본적으로 없기 때문에
// 정삭적인 작동이 되지 않을 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

int n, temp;
vector<int> v;

int main()
{
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for(int i = 0; i < n; i++)
	{
		cin >> temp;
		v.push_back(temp);
	}
	
	sort(v.begin(), v.end());
	for(int val : v) cout << val << "\\n";
  return 0;
}

후기

처음에 정답률이 너무 낮아서 sort함수로 하면 실패하는 문제인가 의심했었다. 10분정도 고민 후 방법이 떠오르지 않아 sort함수로 제출했는데, 정답이라고 떠서 놀랐었다. 생각보다 많은 사람들이 STL활용을 안한다는 것을 짐작하게 되었고, 시간이 중요한 코딩테스트에서 시간을 조금이라도 줄이기 위해서는 STL사용법을 부지런히 익혀야겠다고 다짐했다.