백준 2751 번 문제 풀이 C++ :수 정렬하기 2

#76. 백준 2751번 문제 풀이: 수 정렬하기 2

N개의 수가 주어졌을 때, 오름차순으로 정렬하는 프로그램을 작성하시오. 입력: 첫줄에 수의 개수(1 ≤ N ≤ 1,000,000). 둘째 줄부터 한 줄에 하나씩 N개의 수가 주어진다. 이 수는 절댓값은 1,000,000보다 작거나 같은 정수이며 중복되지 않는다. 출력: N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력.

입력/출력

--입력--
5
5
4
3
2
1
--출력--
1
2
3
4
5

문제풀이+해설

이 문제는 단순히 소팅을 하는 것 처럼 보인다. 
하지만 대부분 시간초과라는 결과를 맞게 될 것이다.

한 줄에 하나씩 최대 1,000,000개의 입력 처리가 시간내에 가능해야 하기 때문에 입력처리 속도를 줄이는 방법으로 코딩하는게 이번 문제의 의도이다.
프로그래밍 언어마다 입출력 방식은 여러가지가 있다.

소팅은 각 언어에서 기본으로 제공하는 소팅함수들을 사용

파이썬: 
 일반적으로 input(),속도를 위해 getline() 함수를 사용해야 한다.
C/C++ 언어:
 이번 문제에 한해서 기본 입력함수 scanf 나 cin 으로도 충분히 빠르기 때문에 그냥 사용하면 된다.

code sol.

코드편집/실행

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

int main() {
  int i, n;
  int N; //수의 개수 변수
  vector<int> ns; // 수를 입력 받을 벡터배열
  cin >> N; // 수의 개수 입력받음.
  for(i = 0; i< N; i++) { // 주어진 N개 만큼 입력 받음
    cin >> n; // 숫자를 입력받아..
    ns.push_back(n); // 그 숫자를 벡터에 넣음.
  }
  sort(ns.begin(), ns.end()); // sort 로 배열 소팅
  for(i = 0; i < N; i++) {
    cout << ns[i] << "\n"; // 한줄에 하나씩 출력
  }
  return 0;
}