글 읽기 - 3649 로봇프로젝트 set으로 풀기 시간초과 질문입니다!

tpwls1213 4년 전 0

이 문제를 아래 코드처럼 set으로 풀었습니다

들어오는 n개의 수를 다 set에 넣어두고

set에 있는 수로 다 조합해보고 찾는 방식으로 했는데

어차피 최대 set크기만큼 볼거라고 생각하고 짰는데 50퍼에서 시간초과가 나네요..!

혹시 어디가 잘못되었을까요..!

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
using namespace std;
set<int> s;
vector<pair<int,pair<int,int>>> vt;
int x,n;
int main(){
    //freopen("input.txt","r",stdin);
    int t;
    while(scanf(" %d",&t) != -1){
        t*=10000000; vt.clear();
        scanf(" %d",&n);
        for(int i=0;i<n;i++){
            scanf(" %d",&x);
            s.insert(x);
        }
        while(!s.empty()){
            auto num = *s.begin();
            s.erase(num);
            int c = t-num;
            if(s.count(c)){
                vt.push_back({abs(num-c),{min(c,num),max(c,num)}});
                s.erase(c);
            } 
        }

        sort(vt.begin(),vt.end());
        reverse(vt.begin(),vt.end());
        if(vt.size()){
            printf("yes %d %d\n",vt[0].second.first,vt[0].second.second);
        } else {
            puts("danger");
        }
    }
}

windflower 4년 전 1

시간복잡도가 n(logn)^2이여서 위험한데 test case까지 있으니까 시간 초과 나지 않을까요?

tpwls1213 4년 전 0

흑 그러게요 ㅠㅠ 그냥 이분탐색으로 풀면되는데 시간 5초라 충분히 들어갈거라 생각해서 쓸데없이 열심히 도전했습니다 ㅠ

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

문제

문제

출처

ICPC

3649 로봇프로젝트 set으로 풀기 시간초과 질문입니다!

tpwls1213 4년 전 0

windflower 4년 전 1

tpwls1213 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말