[백준알고리즘] 10989번: 수 정렬하기 3 -C++

[백준알고리즘] 10989번:  수 정렬하기 3 -C++

10989번: 수 정렬하기 3 (acmicpc.net)

10989번: 수 정렬하기 3

이번에는 지난 '수 정렬하기 2'에서 겪었던 시간 초과 잔혹사를 보내지 않기 위해서 처음부터 ostringstream을 사용해서 문제를 풀었다. 그런데 예상치 못한 문제들을 겪었다.

 

아래는 그때 고난을 겪었던 '수 정렬하기 2'의 링크이다.

[백준알고리즘] 2751번: 수 정렬하기 2 -C++ (tistory.com)

 

'수 정렬하기 2'와 달라진 점은 정렬할 수의 범위는 줄어들었지만, 정렬할 수의 개수는 매우 늘어났다는 것이다.

그러면서 동시에 메모리가 8MB로 제한되어 있다.

 

메모리 8MB는 \(10,000,000\)개의 수를 모두 저장할 수 없는 수지만, \(10,000\)의 범위 안에서는 저장할 수 있는 방법이다.

 

따라서 '수 정렬하기 2'를 풀때도 사용했던 방법 중 하나로, 카운팅 정렬 (Counting Sort)를 할 것이다. 입력이 들어올 수 있는 범위 전체에 대해 배열을 확보한 뒤, 각 수가 얼마나 입력됐는지 확인하는 것이다. 

이후 입력이 끝나면 작은 숫자부터 큰 숫자로 살피면서 각 숫자가 입력된 횟수만큼 출력해주면 된다.

 

---

2022.02.27

오랜만에 알고리즘을 다시 풀기 시작하려고 한다! 그래서 쉬운 것부터 하려고 골랐는데, 이게 걸렸다!

그래서 오늘 푼 코드를 첨부한다.

 

요즘은 회사에서 푸는 코드 스타일대로 적응했기 때문에 회사 코드 스타일대로 작성해서 올린다.

 

이전에 푼 코드를 보니 거의 동일하게 풀었다. 쓸데없는 것 때문에 시간 초과 발생했던 것 같다. 맨 마지막에 있는 코드가 가장 깔끔하고 쉽게 푼 것 같은데, 오늘 풀었을 때는 set과 array를 사용해서 통과했다.

#include <cstdio>
#include <set>

void solve(void);

int main(void) {
	solve();

	return 0;
}

void solve(void) {
	// 입력
	unsigned int uiNum = 0;
	scanf("%u", &uiNum);

	unsigned int arrValCnt[10001] = { 0, };
	std::set<unsigned int> mapVal;
	std::set<unsigned int>::iterator itVal;
	for ( unsigned int uiCnt = 0; uiCnt < uiNum; ++uiCnt ) {
		unsigned int uiVal;
		scanf("%u", &uiVal);

		itVal = mapVal.find(uiVal);
		if ( mapVal.end() == itVal ) {
			mapVal.insert(uiVal);
		}
		arrValCnt[uiVal]++;
	}

	// 출력
	for ( itVal = mapVal.begin(); itVal != mapVal.end(); ) {
		for ( unsigned int uiCnt = arrValCnt[*itVal]; uiCnt > 0; --uiCnt ) {
			printf("%u\n", *itVal);
		}
		
		mapVal.erase(itVal++);
	}
}

---

 

아래 코드는 통과한 코드는 아니고, 처음에 시도했던 코드다. 앞서 언급했던대로 ostringstream을 사용했다. 

그런데, 예상치 못하게 메모리초과가 발생했다.

#include <iostream>
#include <sstream>

void solve(void);

int main(void)
{
	solve();
}

void solve(void)
{
	int n;
	std::cin >> n;

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

	std::ostringstream oss;
	for (int i = 1; i <= 10000; i++)
		for (int j = 0; j < num[i]; j++)
			oss << i << '\n';

	std::cout << oss.str();
}

 

나는 다른 분들의 코드를 보고 왜 메모리 초과가 발생하는지 몰랐다. 똑같이 크기 \(10,000\)의 배열을 주고, 카운팅 정렬을 사용했기 때문이다.

 

하지만 내가 간과한 것이 있었는데, 바로 ostringstream을 통해 출력버퍼에 저장하는 스트림의 크기이다.

 

출력 스트림에 들어갈 수 있는 최대 문자열의 크기는 8MB를 초과한다.

출력 스트림에서 한 줄당 [1, 0, 0, 0, 0, '\n'] 총 6바이트가 필요하게 되는데, \(10,000,000\)개의 입력되는 숫자가 모두 \(10,000\)이라면 \(60,000,000\)바이트의 크기의 출력 스트림을 갖게 되는 것이다.

당연히 이 크기는 메모리 범위를 넘어서 메모리초과를 일으킨 것이다.

 

그러다 보니 출력을 바로 cout을 통해 해주게 되었고, 이때는 시간 초과가 발생할 것을 예상하고 있었다.

 

그래서 ios:sync_with_stdio(false);를 통해 iostream과 cstdio의 동기화를 끊어줌으로써 속도를 향상했고, cin.tie(NULL);을 통해서 cin과 cout의 연결도 끊어주어 속도를 향상시켰다.

(그러나 이 방법들은 싱글 스레드 환경에서만 사용해야 하는 제약이 있다고는 한다. 잘 모르기 때문에 아래 참고 링크들을 살펴보고 찾아봐야겠다.)

 

#include <iostream>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	solve();
}

void solve(void)
{
	int n;
	std::cin >> n;

	int num[10001] = { 0, };
	for (int i = 0; i < n; i++)
	{
		int temp;
		std::cin >> temp;
		num[temp]++;
	}
	
	for (int i = 1; i <= 10000; i++)
		for (int j = 0; j < num[i]; j++)
			std::cout << i << '\n';
}

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

---

[참고]

cin, cout 입출력 속도 빠르게 하는 방법 :: 코딩 잘하면 학교에서 인싸되나요? (tistory.com)

ios_base::sync_with_stdio(false); cin.tie(NULL); 의 의미 (tistory.com)