[백준] 2751번 : 수 정렬하기 2 (C++) + 시간초과 & 런타임 에러(OutofBounds) 해결

 

---

문제

---

풀이

첫 번째 코드 - 실패 

 ➡ 시간복잡도: O(n²), int 배열 사용

  

// O(n^2), 시간초과 & 배열의 크기가 커 오류 발생

#include <iostream>
#include <string>
using namespace std;

int main() {
	int N, num, temp;		
	int arr[1000001];

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> num;
		arr[i] = num;
	}

	for (int i = 0; i <= N - 2 ; i++) {
		for (int j = i + 1; j <= N - 1; j++) {
			if (arr[i] > arr[j]) {
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		cout << arr[i] << "\n";
	}

	return 0;
}

 

 

배열을 이용해 입력된 숫자를 저장하고, 오름차순으로 정렬하는 코드를 만들었다.

하지만, 시간 초과 및 입력값이 많아 배열의 범위를 넘어서 런타임 에러(OutofBounds)가 발생했다.

 

 

1. 시간 초과 이유: 이중 for문을 사용하여, O(n²)의 시간복잡도를 갖는다. 따라서, 시간이 너무 오래 걸린다.

 

• Insertion, Bubble, Selection Sort의 평균 시간 복잡도 = O(n²)
• Quick, Merge, Heap Sort의 평균 시간 복잡도 = O(nlogn)

 

따라서, 두 번째 풀이에는 C++에 내장된 sort 함수를 이용하였다. Quick Sort 기반이기 때문에 최악의 경우 O(n²)가 아니라면, O(nlogn)의 시간복잡도가 나올 것이다. sort()는 C++의 algorithm 헤더에 포함되어 있다.

 

 

2. 런타임 에러 이유: 입력되는 N의 값이 최대 1,000,000개이다. int array의 최대 크기는 약 250,000이기 때문에, 배열의 범위를 넘어서 OutofBounds 에러가 발생한다.

 

• int 배열의 최대 크기 =  약 250,000 (이십오만)
• vector의 최대 크기 = 약 100,000,000 (1억)

추가로, array를 사용하기 위해서는 원소의 개수를 지정해야한다.

vector는 원소의 개수를 지정하지 않더라도, 선언할 수 있다.

 

따라서, 두 번째 풀이에는 vector를 이용하였다. vector의 범위를 입력값이 넘어서지 않기 때문에, 런타임 에러가 발생하지 않는다. vector를 사용하기 위해서는 C++의 vector 헤더를 사용해야 한다.

 

더하여, endl이 아닌 \n을 사용하였다.

endl은 출력 스트림에 사용되는 버퍼를 매번 비우므로(buffer flush) 시간이 오래 걸린다. 따라서, \n을 사용하면 시간을 단축시킬 수 있다.

---

두 번째 코드 - 성공  

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

int main() {
	int N, num;
	vector<int> v;

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> num;
		v.push_back(num);
	}

	sort(v.begin(), v.end());

	for (int i = 0; i < N; i++) {
		cout << v[i] << "\n";
	}

	return 0;
}

---

결과