[AC] 10989 수 정렬하기 3

출처 : https://www.acmicpc.net/problem/10989

https://github.com/stemp12/study/blob/master/acmicpc.net/2016.02/10989.cpp

정답 : 

문제를 보면 인풋이 천만개이다. 그리고 더 읽어보면 10,000보다 작거나 같은 자연수라고 한다. 즉, 10000개의 숫자들을 가지고 천만개를 입력하게 되니 반드시 중복이 있다는 말이다. 

이 부분을 캐치해야 문제를 풀 수있다. 나는 맵을 사용하여 풀었는데, 맵을 사용하지 않고도 풀 수있다.

맵을 사용하지 않는다면 어차피 숫자는 10000개니까 bool 함수를 써서 인풋이 들어오면 그 부분을 참으로 맞춘다.

그리고 int배열을 하나만들고 해당 부분을 카운팅해준다.

입력이 끝나면 for(1만) 을 돌려서 bool이 참이면 그에따른 int배열의 개수만큼 그 수를 출력해주면된다. 

결국 입력은 천만번이지만 정렬도 없고 그냥 포문 1만번으로 답을 구할수있다.

그리고 이런 문제의 경우 인풋도 출력도 엄청많은데 cin, cout보다는 scanf와 printf를 센스있게 써줘야한다. 

속도면에서 엄청난 차이가 있다.