글 읽기 - 연결 리스트를 이용해 문제를 풀었는데 95%에서 시간 초과가 뜨네요

lucian0910 6년 전 0

어떤 부분이 잘못되어있는 것일까요? 테스트 케이스 다 가져다 썼을 때는 다 맞게 나왔습니다.

#include <stdio.h>
#include <stdlib.h>

typedef struct _node{
    int data;
    struct _node * next;
}Node;

int main(){
    int n,k;
    int i;
    int leNum;
    int num=0;
    int flag=1;

    while(1){
        scanf("%d %d", &n, &k);
        if(k>=2 && n>k && n<=1000)
            break;
    }

    Node * head = NULL;
    Node * tail = NULL;
    Node * before = NULL;

    Node * newNode = NULL;

    head = (Node*)malloc(sizeof(Node));//head는 더미 데이터
    tail = head;

    /*연결 리스트 생성(2부터 n까지 생성)*/
    for(i=2; i<=n; i++){
        newNode = (Node*)malloc(sizeof(Node));
        newNode->data=i;
        newNode->next=NULL;

        tail->next = newNode;
        tail = newNode;
    }

    /*연결 리스트에서 head 다음 부분이 제일 작은 숫자이므로 이를 기준으로 순차적으로 수를 없앤다.*/
    while(flag){
        Node * curNode = head;
        Node * nextNode = head->next;

        leNum = nextNode->data;

        do{
            before = curNode;
            curNode = nextNode;
            nextNode = nextNode->next;
            if((curNode->data)%leNum==0){//만약 에라토스테네스 체에 걸러진다면
                num++;
                if(num==k){//만약 k라는 기준에 도달한다면
                    printf("%d \n", curNode->data);
                    flag=0;
                    break;
                }
                before->next=nextNode;//전 노드와 다음 노드와 연결 작업
                free(curNode);
            }
        }while(nextNode != NULL);//끝에 도달할때까지 반복
    }

    /*남은 연결리스트 free 시키는 작업*/
    if(head == NULL)
        return 0;
    else{
        Node * delNode = head;
        Node * delNextNode = head->next;

        while(delNextNode != NULL){
            delNode = delNextNode;
            delNextNode = delNextNode->next;

            free(delNode);
        }
    }
    return 0;
}

djm03178 6년 전 0

조건에 맞지 않는 입력이 마지막 케이스에 있는 것 같습니다. 18번째 줄을 주석처리하니 맞게 나오네요. 지금은 폰이라 좀 뒤에 집 가서 자세히 봐야겠네요.

lucian0910 6년 전 0

근데 원래 18번째 줄은 문제에서 나온 조건(2<=k<n<=1000)을 그대로 적은 것 아닙니까? 이 줄을 없애서 맞게 나오는 건 뭔가 범위에 안 맞는 조건이 테스트 케이스에 들어있는 것이라고 해석해야할까요?

djm03178 6년 전 0

k=1인 케이스가 있는 것 같네요. 데이터 수정을 요청해야 할 것 같습니다.

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

문제

문제

출처

ICPC

연결 리스트를 이용해 문제를 풀었는데 95%에서 시간 초과가 뜨네요

lucian0910 6년 전 0

djm03178 6년 전 0

lucian0910 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말