• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

배열이 아니라 벡터를 이용해봤는데, 시간 제한 초과가 나는 이유가 궁금합니다.

20.06.07 14:12 작성 조회수 184

1

안녕하세요 선생님.  

선생님께서는 39번 문제 풀때 배열을 이용하셨지만 제가 먼저 풀어볼때는 벡터를 썼고 문제의 입출력예시는 알맞게 동작을 했었습니다. 그러나 채점폴더에서는 테스트케이스 5개 전부 시간초과가 났습니다. 

제 코드는 아래와 같습니다. 

어떤 부분이 잘못된 것이고 어떻게 고쳐야 할지 궁금합니다.

감사합니다. 

int main(int argc, char** argv){
	
	// 배열의 크기 저장, 인덱스를 저장하는 변수 3개 (p) 셋 다 1로 시작함.  
	int a_size, b_size, arr_size, i, p1=1, p2=1, p3=1; 
	
	//freopen("input.txt", "rt", stdin);
	
	// 필요한 배열 3개 : 입력받는 배열 arr_a, arr_b, 결과배열 res 
	 
	// 입력받기 시작  
	scanf("%d", &a_size);
	vector<int> arr_a(a_size);
		
	for(i=1; i<=a_size; i++){  // 벡터에 숫자를 입력받는 인덱스를  1 부터 하고 있음.  
		scanf("%d", &arr_a[i]);
	}
	
	scanf("%d", &b_size);
	vector<int> arr_b(b_size);
		
	for(i=1; i<=b_size; i++){ 
		scanf("%d", &arr_b[i]);
	}// 입력받기 끝  
	
	// 결과 저장할 벡터  
	vector<int> res(a_size+b_size);

	// 인덱스 변수 2개를 가지고 작은 수가 나올 때 마다 p1 또는 p2를 이동시킴. 
	while(p1 <= a_size && p2 <= b_size){ // 어느 한 쪽이 자기 크기보다 커질 때까지. 
		
		if(arr_a[p1] < arr_b[p2]){
			res[p3++] = arr_a[p1++]; 
			// p3를 대입한 후에, 1증가 해준다. res[p3]; p3+=1; 과 같다.  
		}else{
			res[p3++] = arr_b[p2++]; 
		}
	}
	
	// 한 쪽은 다 res에 들어가고, 다른 한 쪽은 res에 못들어가고 남았을 것. 
	while(p1 <= a_size) res[p3++] = arr_a[p1++];
	while(p2 <= b_size) res[p3++] = arr_b[p2++];

	for(i=1; i<=a_size+b_size; i++){ // 출력 할 때도 인덱스 1부터 시작. 
		printf("%d ", res[i]);
	}
	
	return 0;
}

답변 1

답변을 작성해보세요.

2

김태원님의 프로필

김태원

지식공유자

20.06.07 20:51

안녕하세요^^

인덱스 번호를 1번부터 사용하려면 벡터선언할 때 크기를   vector<int> arr_a(a_size+1); 와 같이 하세요. 다른 벡터도 마찬가지입니다.