Inflearn Community Q&A
asked
46번) 벡터로 배열생성시 시간초과 문제
Resolved
Written on
·
389
0
강의처럼 전역변수로 배열 a[2001]로 선언하면 시간초과문제가 생기지 않습니다.
그런데 변수선언을 벡터로 했더니 4,5번 케이스에서 시간초과 문제가 발생했습니다.
Q1. 제가 코테를 시작한지 얼마 안되서... 혹시 일반적인 프로그래밍 말고 코딩테스트를 보는 경우, 메모리 절약보다는 실행시간을 고려하는게 더 중요한가요??
Q2. 변수선언 방법에는, a[2001]처럼 크게 잡는 것과 new로 동적할당하는 것과 vector를 쓰는 것 . 이렇게 3가지 정도 알고 있습니다. 이 중에서 상황에 따라 어떤 방식을 선택하는 지 등의 기준(?)이 있을까요?
C++코테 준비 같이 해요!
Answer 4
0
0
0
스스로 스터디
Questioner
답변 감사합니다!
제가 스스로 짠 코드는 아래에 첨부했는데, 바뀐 부분은
전역변수 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;
}
0
codingcamp
Instructor
1. 공간복잡도보다는 시간복잡도를 우선으로 하는게 좋을 것 같습니다. 그렇다고 공간복잡도를 무시해서는 안됩니다.
2. 요즘은 거의 모두 vector를 이용합니다. 전역변수로 했을 때는 통과하고 벡터로 해거 4, 5번이 시간초과 났다는게 좀 이상하네요. 벡터로 짠 코드를 보고 싶네요.