46번) 벡터로 배열생성시 시간초과 문제

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

46. 멀티 태스킹

해결된 질문

작성

343

강의처럼 전역변수로 배열 a[2001]로 선언하면 시간초과문제가 생기지 않습니다.

그런데 변수선언을 벡터로 했더니 4,5번 케이스에서 시간초과 문제가 발생했습니다.

Q1. 제가 코테를 시작한지 얼마 안되서... 혹시 일반적인 프로그래밍 말고 코딩테스트를 보는 경우, 메모리 절약보다는 실행시간을 고려하는게 더 중요한가요??

Q2. 변수선언 방법에는, a[2001]처럼 크게 잡는 것과 new로 동적할당하는 것과 vector를 쓰는 것 . 이렇게 3가지 정도 알고 있습니다. 이 중에서 상황에 따라 어떤 방식을 선택하는 지 등의 기준(?)이 있을까요?

C++코테 준비 같이 해요!

답변 4

스스로 스터디

질문자

넵 알겠습니다. 답변 감사합니다!

김태원

지식공유자

제 컴퓨터에서는 위 코드가 가볍게 100점 나옵니다. 이상하네요. 노트북의 성능을 따질만한 속도도 아닌 엄청 빠르게 4번, 5번이 통과됩니다.

스스로 스터디

질문자

답변 감사합니다!

제가 스스로 짠 코드는 아래에 첨부했는데, 바뀐 부분은

전역변수 int a[2001]; 대신에

main문 안에 std::vector<int> a(n + 1); 입니다.

음.. 선생님께서 공유해주신 소스파일 코드에도 저 부분만 수정해서 실행해봤는데

4,5번 케이스에서 시간초과가 발생했습니다. 그렇다면... 혹시 노트북 성능 문제일까요??;;

#include <vector>
//int a[2001]; <- 이거 대신에
int main() {

	int i, n, pos = 0, sum = 0, k = 0;
	scanf("%d", &n);
	std::vector<int> a(n + 1); // <- 이렇게 했습니다.

	// 작업량 in
	for (i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		sum += a[i];
	}

	// k초 후 정전
	scanf("%d", &k);

	// 작업 완료 후 정전이 되면 -1출력
	if (sum <= k) {
		printf("-1");
		return 0;
	}

	// 정전 전까지 작업량 카운트 해야함.
	int sec = 0;
	while (1) {
		pos++;
		if (pos > n) pos = 1;
		if (a[pos] == 0)continue;
		a[pos]--;
		sec++;
		if (sec == k) break; //k초 되면 정전
	}

	// 전기가 들어오면 어디부터 작업하나? pos+1부터.
	while (1) {
		pos++;
		if (pos > n) pos = 1;

		if (a[pos] != 0) break;//남은 작업의 위치는 pos
	}

	printf("%d", pos);
	return 0;
}

김태원

지식공유자

1. 공간복잡도보다는 시간복잡도를 우선으로 하는게 좋을 것 같습니다. 그렇다고 공간복잡도를 무시해서는 안됩니다.

2. 요즘은 거의 모두 vector를 이용합니다. 전역변수로 했을 때는 통과하고 벡터로 해거 4, 5번이 시간초과 났다는게 좀 이상하네요. 벡터로 짠 코드를 보고 싶네요.

인프런 커뮤니티 질문&답변

46번) 벡터로 배열생성시 시간초과 문제