글 읽기 - [C++] 입력방식에 따른 시간초과, 고수님들 도와주세요

ryuflower 3년 전 0

안녕하세요, c++을 사용해서 같은 알고리즘을 사용했는데 입력받는 방식에 따라 하나는 통과, 하나는 시간초과로 뜹니다.

혹시 어떤 차이에서 발생하는지 알려주실 수 있으실까요.

통과하는 입력 : string으로 한줄 씩 받은후 int map에 값을 복사 한후 비교할때 int 값으로 비교.

시간초과하는 입력 : char로 하나씩 입력 받은후 비교할때 char값으로 비교

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(void){
    int N,M,i,j,k,flag=0,check,tmpi,tmpj,ans=0;
    int dir[3][2]={{1,1},{1,0},{0,1}};
    cin >> N >> M;
    vector <string> data(N);
    vector <vector <int> > map(N, vector<int> (M));
    cin.ignore();
    for(i=0;i<N;i++) getline(cin,data[i]);
    /* 시간초과되는 입력
     for(i=0;i<N;i++){
//         for(j=0;j<M;j++){
//             scanf("%c",&map[i][j]);
//             if(map[i][j]=='1') flag= 1;
//         }
//     }
\*/
    for(i=0;i<N;i++){
        for(j=0;j<M;j++){
            if(data[i][j]=='1'){
                flag=1;
                map[i][j]=1;
            }
            else map[i][j]=0;
        }
    }
    if(flag==0) cout << "0\n";
    else{
        flag=1;
        while(1){
            flag=0;
            for(i=0;i<N;i++){
                for(j=0;j<M;j++){
                    if(map[i][j]==1){
                        check = 0;
                        for(k=0;k<3;k++){
                            tmpi=i+dir[k][0];
                            tmpj=j+dir[k][1];
                            if(tmpi<N && tmpj<M && map[tmpi][tmpj]==1){
                                check++;
                                
                            }
                        }
                        if(check==3) flag=1;
                        else map[i][j]=0;
                    }
                }
            }

            // cout << "\n" ;
            // cout << "ans: " << ans << ",  flag : " << flag << ",  N : " << N << " , M : " << M << "\n";
            // for(i=0;i<N;i++){
            //     for(j=0;j<M;j++) cout << map[i][j];
            //     cout << "\n";
            // }

            if(flag==1) ans++;
            N--;
            M--;

            if(N<1) break;
            if(M<1) break;
            if(flag!=1) break;
    }
    cout << (ans+1)*(ans+1) << "\n";
    }
 
    return 0;
}

hoxymola 3년 전 0

djm03178 3년 전 2

그만큼 scanf로 %c로 한 글자씩 입력받는 게 느리다고 그대로 받아들이시면 될 것 같습니다. 코드의 로직이 이미 n^3인 것 같아서 통과된 코드도 아슬아슬하기 때문에 약간만 더 느린 입력을 쓰더라도 시간 초과가 되는 것이 이상하지 않습니다.

그보다 정확히 어떻게 바꾸셨다는 건지 잘 모르겠네요. 해당 주석 부분만 해제하고 14번째 줄을 지우는 것으로는 틀렸습니다가 나옵니다. 질문 시에는 맞은 코드보다는 틀린 코드를 우선적으로 온전하게 올려주시는 편이 좋습니다.

ryuflower 3년 전 1

감사합니다.

%c가 훨씬 느리군요.

다음번 질문때는 말씀해주신 내용 참고하도록 하겠습니다.

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

문제

문제

출처

ICPC

[C++] 입력방식에 따른 시간초과, 고수님들 도와주세요

ryuflower 3년 전 0

hoxymola 3년 전 0

djm03178 3년 전 2

ryuflower 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말