[허언증/코딩] 백준(Baekjoon)_10989 수 정렬하기3 (C++)

안녕하세요. 허언증 입니다.

 

저같은 경우 C++로  풀었습니다. 

python, Java로 안 풀었어요!!

 

 

문제

 

 

10989번: 수 정렬하기 3

---

■ 문제 조건 ■

시간 제한 : 시간 복잡도 - 시간 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

 

 

 

 

참고

 

입력 속도 비교 표(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);

https://www.acmicpc.net/board/view/8074