글 읽기 - [C++] sort() 함수와 이진탐색으로 풀었는데 시간초과가 납니다.

swj0324 2년 전 0

c++ sort함수(nlogn) 과 반복문안에 이진탐색(n * logn) 으로 푼 것 같은데 시간초과가 납니다.

어디가 문제인 걸까요?

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>


int main(){

	int n;
	std::cin >> n;
	std::vector<int> trait;
	int value;
	
	for(int i=0; i<n; i++){
		std::cin >> value;
		trait.push_back(value);
	}
	std::sort(trait.begin(), trait.end());
	
	int best = 2000000001;
	int solution_1_idx = -1;
	int solution_2_idx = -1;
	
	bool done = false;
	
	for(int i=0; i<n-1; i++){
		int lo= i+1;
		int hi = n-1;
		while(lo<=hi){
			int mid = (lo+hi)/2;
			int mixed_trait = trait[i] + trait[mid];
			if(std::abs(best)>std::abs(mixed_trait)){
				best = mixed_trait;
				solution_1_idx = i;
				solution_2_idx = mid;
			}
			if(mixed_trait<0){
				lo = mid+1;
			}
			else if(mixed_trait>0){
				hi = mid-1;
			}
			else{
				done = true;
			}
		}
		if(done){
			break;
		}
	}

	std::cout << trait[solution_1_idx] << " " << trait[solution_2_idx] << std::endl;
	
	return 0;
}

palilo 2년 전 1

15552번: 빠른 A+B (acmicpc.net)

이 문제 먼저 풀어보세요

swj0324 2년 전 0

std::ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);

를 넣고 안넣고가 문제 정답 여부에 영향을 준다는 것을 알아서

2470번 문제에 std::ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); 를 추가해서

돌렸는데도 똑같이 시간초과가 납니다..

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>


int main(){
	
	std::ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);
	
	int n;
	std::cin >> n;
	std::vector<int> trait;
	int value;
	
	for(int i=0; i<n; i++){
		std::cin >> value;
		trait.push_back(value);
	}
	std::sort(trait.begin(), trait.end());
	
	int best = 2000000001;
	int solution_1_idx = -1;
	int solution_2_idx = -1;
	
	bool done = false;
	
	for(int i=0; i<n-1; i++){
		int lo= i+1;
		int hi = n-1;
		while(lo<=hi){
			int mid = (lo+hi)/2;
			int mixed_trait = trait[i] + trait[mid];
			if(std::abs(best)>std::abs(mixed_trait)){
				best = mixed_trait;
				solution_1_idx = i;
				solution_2_idx = mid;
			}
			if(mixed_trait<0){
				lo = mid+1;
			}
			else if(mixed_trait>0){
				hi = mid-1;
			}
			else{
				done = true;
			}
		}
		if(done){
			break;
		}
	}

	std::cout << trait[solution_1_idx] << " " << trait[solution_2_idx] << "\n";
	
	return 0;
}

palilo 2년 전 1

done = true; 로 만들고 아무것도 하지 않습니다.

즉, lo랑 hi값이 그대로에요. 무한루프가 생깁니다.

아마 done = true; 아래에 break;를 넣으면 시간 초과는 피할 겁니다.

swj0324 2년 전 0

알려주셔서 감사합니다.

시간복잡도도 문제없었는데 왜 시간초과가 나는지 고민했었는데

done = true 아래에 break를 안넣어서 시간초과가 났었던 거군요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C++] sort() 함수와 이진탐색으로 풀었는데 시간초과가 납니다.

swj0324 2년 전 0

palilo 2년 전 1

swj0324 2년 전 0

palilo 2년 전 1

swj0324 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말