[beakjoon-10989-C++] 수 정렬하기3

문제

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

※메모리 제한 : 8MB 시간 제한 : 5.0sec

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

코드

해당 문제는 제한 시간과 메모리가 없을 경우 굉장히 쉽다.

필자도 처음에는 Vector와 sort 함수를 사용하여 코드를 짯다.

결과는 메모리 초과로 오답을 맞이했다.

10,000,000개의 int형 data를 받아들일 경우, 40,000,000byte가 되며 40MB로 제한 메모리를 넘어서게 된다.

 

이 문제를 해결하기 위해 vector(또는 다른 자료구조)에 저장하는 것이 아니라 배열을 하나 만들어 index를 숫자로 생각하고 해당 숫자의 개수를 집어넣었다.이 경우 10000개의 int형 data를 사용하므로 4MB로 제한 메모리를 절반만 사용하고도 자료를 저장할 수 있다.

 

다음 문제는 제한 시간이다.cout, cin의 출력, 입력 버퍼 스트림은 c의 printf scanf 와의 충돌을 막기 위해 동기화 되어 있다.이로 인해 iostream과 stdio의 버퍼를 모두 사용하기 때문에 시간 딜레이가 생기게 된다. 이러한 시간을 줄이기 위해 iosbase::sync_with_stdio(false); 코드를 사용해 동기화를 풀어주었습니다.

 

다음으로는 개행문자입니다.

전 습관적으로 endl을 이용하여 출력을 끝내는 버릇이 있습니다.

하지만, endl의 경우 출력 버퍼를 비우게 되기 때문에 매 줄마다 버퍼를 비우기위해 시간을 투자하게 됩니다.

반면에 \n 개행문자의 경우 버퍼를 비우지 않고 개행을 하기 때문에 버퍼를 비우는 시간을 아낄 수 있어 실행 시간을 줄일 수 있습니다.