[허언증/코딩] 백준(Baekjoon)_10989 수 정렬하기3 (C++)
안녕하세요. 허언증 입니다.
저같은 경우 C++로 풀었습니다.
python, Java로 안 풀었어요!!
문제
10989번: 수 정렬하기 3
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
www.acmicpc.net
■ 문제 조건 ■
시간 제한 : 시간 복잡도 - 시간 3초
메모리 제한 : 공간 복잡도 – 메모리 8MB
정답 비율 : 22%
메모리 ,시간 제한 둘다 고려를 해야 해서 어려운 문제인거 같다.
메모리 오버 에러 당연히 / 시간 오버 에러 당연히 경험했다.
두 가지의 경우를 다 겪고 결국 해결 했다.
다른 분들도 이 글을 보고 참고가 되었으면 합니다!!!
1. 메모리 오버 > 2. 시간 오버 > 3. 해결
순으로 글을 작성 했습니다.
★★★메모리 오버★★★
메모리 제한 : 공간 복잡도 -메모리 8MB
sort library
http://www.cplusplus.com/reference/algorithm/sort/
-풀이-
int = 4byte
n으로 받으면 최대 입력 데이터 수가 10,000,000일 때 (문제 제시)
메모리 오버 발생 / 4 * 10,000,000 = 38.146973MB / 8MB 충족X
★★★시간오버★★★
시간 제한 : 시간 복잡도 - 시간 3초
-출력시간-
-입력시간-
0.9229 + 2.1742 = 3.0971초 오버!!
★★★통과★★★
Code 6~8
: ios::sync_with_stdio(false); / cin.tie(NULL); / cout.tie(NULL); 코드 추가
-출력시간-
-입력시간-
0.8272 + 2.059 = 2.8862초 통과!!
소스 보기
MinKyungHwi/Baekjoon
C++ Study. Contribute to MinKyungHwi/Baekjoon development by creating an account on GitHub.
github.com
참고
입력 속도 비교 표(10,000,000 기준)
https://www.acmicpc.net/blog/search/%EC%9E%85%EB%A0%A5+%EC%86%8D%EB%8F%84+%EB%B9%84%EA%B5%90
출력 속도 비교 표(10,000,000 기준)
https://www.acmicpc.net/blog/view/57
3가지 사용이유
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);