[C++] 백준 10989번 수 정렬하기 3

 

 

오늘은 중요하신 분들이 오셔서 여러 가지 하느라 이제야 블로그로 출근하였다.

다 풀어버리자~~~~

 

 

 

 

 

 

 

 

 

 

 

...

 

 

문제

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

10989번: 수 정렬하기 3

 

왜 실버 문제만 풀다가 갑자기 브론즈 문제로 넘어갔냐고요??(아 아무 말도 안 했어요?)

그게... 이번에는 어제에 이어 '10816번 숫자 카드 2'를 풀려고 했는데 이것도 옛날에 자바로 푼 적이 있어서 브론즈 문제 하나랑 이 문제 하나 이런 식으로 풀려고 했...으나...

 

생각지도 못한 이 문제가 제 시간을 다 가져갔...

솔직히 문제 봤을 때는 몇 초컷이라고 생각했는데...ㅎㅎ(아니었다..)

 

 

 

//메모리 초과 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> num;

int main() {
	int n, a;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a;
		num.push_back(a);
	}
	sort(num.begin(), num.end());
	for (int i = 0; i < n; i++) {
		cout << num[i] << "\n";
	}

	return 0;
}

 

 

계속 메모리 초과가...발생했다.

여러 가지 시도해 봤지만... 결과는 똑같았다.

 

 

그러다가 그냥 다른 사람의 풀이를 찾아보았다.(https://tooo1.tistory.com/72)

위에 있는 링크를 보고 이해한 다음 내가 코드를 다시 작성했다.

 

 

...

 

 

 

ㅎㅎ...

 

//시간 초과 코드

#include <iostream>
using namespace std;

int num[10001] = { 0 };

int main() {
	int n, a;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a;
		num[a] += 1;
	}
	for (int i = 1; i < 10001; i++) {
		for (int j = 0; j < num[i]; j++) {
			cout << i << "\n";
		}
	}
	return 0;
}

 

 

 

그래서 다시 블로그에 방문하여 확인해 보니...

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

 

C++의 표준 stream의 동기화를 끊는 역할을 해주는 이것을 빼먹었군... 이중 for 문을 작성하며 시간 복잡도에 문제가 생겼다고 한다. (for 문은 O(N)의 시간 복잡도를 가지지만 이중 for문은 O(N^2)의 시간 복잡도를 가진다.)

#include <iostream>
using namespace std;

int num[10001] = { 0 };

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

	int n, a;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a;
		num[a] += 1;
	}
	for (int i = 1; i < 10001; i++) {
		for (int j = 0; j < num[i]; j++) {
			cout << i << "\n";
		}
	}
	return 0;
}

 

 

 

휴....

 

+ 추가) 이 분도 vector를 사용해 sort를 하려고 했더니 메모리 초과가 발생했다고 한다. 공간 복잡도에 문제가 있다고 생각하여 sort() 풀이 방식을 버렸다고 한다. 수의 개수 N은 10000000개이기 때문에 입력값을 전부 저장하면 메모리가 남아나지 않는다.

그래서 입력값을 전부 버리고 입력받을 때마다 해당 배열에 count를 올려 기록하기로 했다고 한다. 난 이게 무슨 소리인지 몰랐었는데 이 분의 코드를 보고 알 수 있었다.

 

=>... 사실 지금까지 공간 복잡도, 시간 복잡도 이런 거는 생각해 본 적이 없다. 이 문제를 통해... 이제는 계산을 해야겠구나 라는 생각이 들었다.

 

다른 사람의 풀이도 보니까 다들 count를 해주는 방식을 사용하였다.(그렇군 그렇군)

 

원래 내 계획은 이거 다 쓴 다음에 원래 풀려고 했던 문제를 풀려고 했으나

오늘 몸 상태가 좀 안 좋은 관계로 오늘은 그냥 여기까지만 해야겠다...

 

그럼 bye bye~~