[백준 / BOJ] 10989번 수 정렬하기 3 (C++, Python)

링크 : https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

---

문제

---

문제 풀이

이전 문제들을 푸는 방식처럼 하면 메모리 초과, 시간 초과 둘 중 하나는 볼 수 있는 문제다. 문제 소개에 '카운팅 정렬'을 사용하라 해서 대충 찾아봤는데 이 링크에서 설명하신 분이 가장 잘하신 것 같아 첨부해본다.

 

우선 sort를 쓰면 메모리 초과가 난다. 그 이유는 입력받는 값이 10,000,000인데 이 정도 크기가 되면.. 제한 조건인 8MB를 훌쩍 초과하기 때문이다. (10^7 * 4byte = 40MB)

 

찬찬히 생각해보면, 조건에서 10,000보다 작거나 같은 자연수라고 명시해주었다. 그렇다면 생각할 수 있는 것은 범위가 정해졌으므로 10,001 크기의 배열을 만들어 입력받은 수의 idx를 하나씩 증가시켜 기록하는 방법이 있을 것이다. 발상이 필요했던 문제인 것 같다. (10,001인 이유는 배열 인덱스는 0부터 시작하지만 작거나 같은 자연수이기 때문에 arr[0] ~ arr[10000]까지 필요하기 때문이다.)

 

그렇게 크기를 기록했다면 이중 for문으로 처음 for문에서 10,001만큼 반복, 나중 for문에서 arr[i] 크기만큼 i를 출력하면 된다.

 

C++ 상세 풀이

C++의 경우에는 아래 코드를 넣지 않으면 시간 초과가 난다.

 

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Python 상세 풀이

sys.stdout.write를 사용해준다.

 

for i in range(N) : 
	arr[int(sys.stdin.readline())] += 1
   
for i in range(10001):
    for j in range(arr[i]):
        sys.stdout.write(str(i) + "\n")

 

C++ 코드 전문

 

Python 코드 전문

 

소감