글 읽기 - [C] 시간 초과 질문입니다.

so4644009 5년 전 0

푸는데 시간 초과가 걸려서 질문 게시판을 보던 중 슬라이딩 윈도우 방식을 이용하면 시간을 줄일 수 있다는 것을 보고 구글링해서 슬라이딩 윈도우 방식을 읽어보고 나름대로 슬라이딩 윈도우로 코드를 짜 보았는데 또 시간 초과가 뜨는 걸로 봐서 제가 슬라이딩 윈도우 방식을 잘못 이해한 것 같아서 올립니다. 어느 부분이 잘못 됐는지 알려주셨으면 좋겠습니다ㅠㅠ

#include <stdio.h>
#include <string.h>
int N,K;
int cnt=0;
typedef struct{
    char name[21];
    int l;
}student; //이름과 이름의 길이를 구조체에 저장
student s[300001];
int main(){
    scanf("%d %d",&N,&K);
    for(int i=0;i<N;++i){
        scanf("%s",s[i].name);
        s[i].l=strlen(s[i].name);
    }
    int sp=0,ep=1;//시작점 인덱스를 sp에 저장하고, ep는 비교할 학생 구조체의 인덱스
    while(1){
        if(sp==N-K){
            break;//시작점 포인터를 가리키는 sp가 N-K이면 루프문 탈출
        }
        else{
            if(ep>sp+K){
                ++sp;
                ep=sp+1;//등수가 K등 초과로 차이나면 시작 포인터를 증가시키고 비교할 학생의 인덱스 또한 시작점 포인터+1로 옮긴다.
            }
            else{
                if(s[sp].l==s[ep].l){
                    ++cnt;
                    ++ep;//길이가 같으면 cnt를 증가시키고 비교대상 인덱스인 ep를 증가시킨다.
                }
                else{
                    ++ep;//길이가 같지 않으면, 인덱스만 증가시킨다.
                }
            }
        }
    }
    printf("%d\n",cnt);
    return 0;
}

so4644009 5년 전 0

방식을 바꾸어서 다시 제출했는데 12%에서 시간 초과가 납니다ㅠㅠ(sp==ep일 때 sp는 1 증가시키고 ep는 1증가한 sp의 값에 K를 추가로 증가시킨 다음 ep포인터를 sp==ep가 될 때까지 이동시키는 방식)

#include <stdio.h>
#include <string.h>
typedef struct{
    char name[21];
    int l;
}student;
student s[300001];
int N;
int K;
int cnt=0;
int main(){
    int sp,ep;
    scanf("%d %d",&N,&K);
    for(int i=0;i<N;++i){
        scanf("%s",s[i].name);
        s[i].l=strlen(s[i].name);
    }
    sp=0;
    ep=K;
    while(1){
        if(sp==N-K){
            break;
        }
        else{
            if(ep-sp==0){
                ++sp;
                ep=sp+K;
            }
            else{
                if(s[sp].l==s[ep].l){
                    ++cnt;
                    --ep;
                }
                else{
                    --ep;
                }
            }
        }
    }
    printf("%d\n",cnt);
    return 0;
}

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

문제

문제

출처

ICPC

[C] 시간 초과 질문입니다.

so4644009 5년 전 0

so4644009 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말