[C++] 백준 10989 수 정렬하기 - 계수정렬(Counting Sort)

#include <iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);

	int countNum[10001]{ 0 };
	int n, i;
	cin >> n;
	
	for (i = 0; i < n; i++)
	{
		int temp;
		cin >> temp;
		countNum[temp]++;
	}

	for (i = 1; i < 10001; i++)
	{
		for (int j = 0; j < countNum[i]; j++)
			cout << i << "\n";
	}
}

 

계수 정렬은 다른 한 배열에 그 수에 대한 개수를 넣은 후

원래의 배열에 개수만큼씩 넣어주면된다.

 

장점으로 비교연산을 따로 하지 않는다는 점이다.

단점으로는 수의 최대값의 크기가 클경우 메모리 낭비가 심하다.

 

이 문제는 배열의 크기가 최대 1000만이나되어 메모리 초과가 될 수도 있기 때문에

배열에 따로 수를 저장하지 않는다.

 

 

 

 

 

힘들었던 점.

이 문제를 푸는데는 오래 걸리지 않았지만 시간초과의 늪에 빠졌다.

 

처음에는 출력과 입력을 cin과 cout으로 해서 계속해보았지만 시간초과가 나서 다른 사람들의 코드를 보면서도

분명같다고 생각했지만 안 되어서 prinf과 scanf로 바꾸어하니까 되긴했다. 그래서 맞은 사람들의 코드를 다시 또

보았는데 cin으로 한사람들이 꽤 있었다. 무슨 문제가 있나해서 여러가지 옮겨적다가 답을 찾았다.

 

ios::sync_with_stdio(false);

이것이 문제였다.

뭔지는 모르겠지만 저것을 사용하여 풀었다.

그 결과로 scanf, printf로 풀은 2524ms의 시간보다 900ms정도 빠른 1668ms의 속도까지 나왔다.

 

참료자료

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

글 읽기 - ios::sync_with_stdio(false); 에 관한 질문입니다!

https://ip99202.github.io/posts/sync_with_stdio(false)-%EC%93%B8-%EB%95%8C-%EC%A3%BC%EC%9D%98%ED%95%A0-%EC%82%AC%ED%95%AD/

sync_with_stdio(false) 쓸 때 주의할 사항

 위 블로그의 내용.

ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
이 코드는 C와 C++의 표준 stream의 동기화를 끊는 역할을 한다.
cin과 cout의 속도가 C의 입출력 속도에 비해 떨어지기 때문에 저 코드를 사용해 속도를 높이는 기능으로 사용한다.
하지만 동기화를 끊게되면 C의 입출력 함수를 더 이상 사용하지 못하는데
그 동안 printf와 scanf만 주의하면 된다고 생각했었는데 getchar도 C에서 쓰이는 입출력 함수이다.
그렇기 때문에 위에 getchar를 사용하지 못해 위의 코드는 틀렸습니다가 나오는 것이다.
비쥬얼스튜디오에서는 동기화를 끊어도 섞어쓰면 알아서 처리해주는 것 같지만 채점프로그램에서는 그렇지 않다.

그렇기 때문에 항상 ios::sync_with_stdio(false);를 쓴다면 C의 입출력을 쓰지않도록 조심해야한다.