글 읽기 - 13414 시간초과 오류가 나는데 이유를 모르겠습니다.

luck3862 7년 전 0

아래 코드가 왜 잘못되었나요?

정말 궁금합니다.

시간초과가 어디서 나는지를 모르겠습니다.

답변 주시면 감사하겠습니다.

#include <iostream>
#include <string>
using namespace std;
int main(){
  int max,attend;
  cin>>max>>attend;
  string stu[attend];
  for(int i=0;i<attend;i++){
    cin>>stu[i];
  }
  for(int i=0;i<attend;i++){
    for(int j=i+1;j<attend;j++){
      if(stu[i]==stu[j]){
        stu[i].clear();
        break;
      }
    }
  }
  int cnt=0;
  for(int i=0;i<attend;i++){
    if(stu[i]!=""){
      cnt++;
      if(cnt<=max){
        cout<<stu[i]<<endl;
      }else{
        break;
      }
    }
  }
  return 0;
}

139 7년 전 0

L의 범위가 500,000까지네요. (위 코드에서는 attend가 되겠죠)

2번째 중첩 for문은 O(n^2)인데, 1초안에 돌리고 싶으시면 더 효율적인 방법을 생각해보셔야할거같아요.

luck3862 7년 전 0

int로 attend를 선언했으면 500000이상 받아 올수 있는 부분 아닌가요???

139 7년 전 1

500000^2 (사실 정확하게말하면 250000*500001) 은 1초안에 안돌아가요.

luck3862 7년 전 1

uppo97님 매번 답변 감사합니다.

제 머리에서는 저렇게 이중 for문을 돌리지 않고는 이 문제를 해결할 방법이 떠오르지 않네요...

혹시 조금이나마 힌트를 주실 수 있으신가요??

luck3862 7년 전 0

아래 소스는 방금 전까지 헠헠대던 소스입니다. ㅎㅎ

#include <iostream>
#include <string>
using namespace std;
int main(){
  int max,attend,valid=0,cnt=0;
  string num;
  cin>>max>>attend;
  string stu[attend];
  for(int i=0;i<attend;i++){
    cin>>stu[cnt];
    for(int j=0;j<cnt;j++){
    	if(stu[j]==stu[cnt]){
    	valid=1;
    	}
    	if(valid){
    		stu[j]=stu[j+1];
    	}
    }
    if(!valid){
    	cnt++;
    }
    valid=0;
  }
  for(int i=0;i<max;i++){
  	cout<<stu[i]<<endl;
  }
  return 0;
}

139 7년 전 0

이소스도 전부 다른 인풋이 들어오는경우 100000*500000으로 시간초과가 나겠네요.

학번정렬로 중복을 제거하는 식으로 접근하시면 괜찮을 것 같아요.

저는 map 이용해서 풀었어요!

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

문제

문제

출처

ICPC

13414 시간초과 오류가 나는데 이유를 모르겠습니다.

luck3862 7년 전 0

139 7년 전 0

luck3862 7년 전 0

139 7년 전 1

luck3862 7년 전 1

luck3862 7년 전 0

139 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말