• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

마지막에서 시간 초과 나오는 이유는 뭘까요?

20.03.17 03:28 작성 조회수 141

0

시간초과가 나오지 않게 하려고 시간복잡도 N^2를 피했는데 마지막에서 시간초과가 나요 왜그럴까요 if에서 배열++하는 작업이 시간이 많이 드는 건가요?

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;
int check[30001];

int main() {
	int N, M;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		check[x]++;
	}
	cin >> M;
	vector<int> arr;
	for (int i = 0; i < M; i++) {
		int x;
		cin >> x;
		if (check[x] > 0) {
			arr.push_back(x);
			check[x]--;
		}
	}
	sort(arr.begin(), arr.end());
	for (int i = 0; i < arr.size(); i++) {
		cout << arr[i] << " ";
	}
	return 0;
}

답변 1

답변을 작성해보세요.

1

check[30001] 배열을 사용해서 배열의 인덱스 번호를 해쉬스타일로 사용할 때는 조심해야 합니다.

이 문제에서 입력되는 값의 크기는 정수형변수의 크기입니다. 즉 입력되는 숫자의 크기가 2147483647까지 들어올 수 있습니다. 그럼 check[2147483648] 로 잡아야 하는데 엄청된 메모리 낭비가 발생하며,  메모리가 너무 많이 잡혀 실제 check배열에 214700000번 인덱스를 접근하려고 하면 접근자체가 안되는 컴퓨터가 많습니다.  

제가 만든 채점 데이터는 숫자의 크기가 백만 이하로 했기 때문에 채점기를 통과하고 싶다면 check[1000001] 정도로 잡고 해보시기 바랍니다. 하지만 영상에서 제가 설명하는 방법으로 푸는게 옳은 방법입니다.