ITES 문제 해결 중 시간싸움

  • yhtgogo
    yhtgogo

    ITES

    문제가 그리 어려운 것은 아니나 시간초과가 상당합니다.

    제가 구현을 선택한 요건(조건)은 아래와 같습니다.
    1. 입력신호를 매번 만들어서 작업을 한다.
    2. 직접 구현한 이상한 큐를 이용한다.
    3. 새로운 신호를 큐에 수집한다.
    4. 새로운 신호를 부분합변수에 누적한다.
    5. 부분합변수에 저장된 값이 K를 넘어서게 되면 큐에서 저장된 가장 오래된 신호값을 추출해 부분합에서 차감한다. 부분합이 K를 초과하는 동안 반복한다.
    6. 부분합이 K와 같으면 카운터 하나를 증가시킨다.
    7. 입력 신호가 종료될때까지 3번부터 반복한다.

    이런 로직이면 O(N^2) 이거든요.
    그래도 돌아가기야 하겠지만.....시간초과납니다.

    제 얕은 지식의 한계로는
    큐를 이용한 동적 메모리를 컨트롤 할 때마다 시간이 더 걸리는 것으로 보입니다.
    그래서 일정크기의 배열로 만들고 그 한도를 넘어서면 더 큰 크기로 재할당을 하는 방법을 생각해보았는데요.

    혹시 다른 꼼수가 있는지요?
    알고리즘으로는 시간을 줄일 방법이 도통 생각나지 않습니다.
    메모리 컨트롤에서 좀 더 시간을 줄이는 것이 좋을 것 같긴해요.
    k값이 5000000 한도이기 때문에 5000000 사이즈의 배열도 생각해봤습니다 ㅎㅎㅎ
    물론 될수 있겠지만 좀 더 동적이고 효율적인 컨트롤은 없는지요?

    소스코드는 입력 신호 한건한건에 대한 동적메모리 할당과 해제를 구현한 것입니다.
    발코딩이므로 참고만 해주세요. ㅠㅠ 

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

typedef struct NODE {
    int data;
    struct NODE* next;
} NODE;
typedef struct LIST {
    int size;
    struct NODE* head;
    struct NODE* tail;
} LIST;

void init_queue(LIST* queue);
int destroy_queue(LIST* queue);
int enqueue(LIST* queue, int data);
int dequeue(LIST* queue, int* data);

int main(){
    LIST q;
    unsigned int a;
    int new_signal, old_signal;
    int i, k, n, sum, counter;
    int test_count;
    ////////////////////////
    //Get TestCase Count
    ////////////////////////
    scanf("%d", &test_count);
    ////////////////////////
    while(test_count--){
        ////////////////////////
        //get k and n
        ////////////////////////
        scanf("%d %d", &k, &n);
        ////////////////////////
        //initialize
        ////////////////////////
        init_queue(&q);
        a = 1983;
        sum = counter = 0;
        ////////////////////////
        //generate signal and find pattern
        ////////////////////////
        for(i = 0 ; i < n ; ++i){
            ////////////////////////
            //generate new signal
            ////////////////////////
            new_signal = (int)(a % 10000) + 1;
            ////////////////////////
            //add new signal
            ////////////////////////
            sum += new_signal;
            enqueue(&q, new_signal);
            ////////////////////////
            //delete old signal, when sum is greater than k.
            ////////////////////////
            while(sum > k){
                dequeue(&q, &old_signal);
                sum -= old_signal;
            }
            ////////////////////////
            //increase counter when sum is equal with k.
            ////////////////////////
            if(sum == k){
                ++counter;
            }
            a = (a * 214013u) + 2531011u;
        }
        printf("%d\n", counter);
        ////////////////////////
        //truncate queue
        ////////////////////////
        destroy_queue(&q);
    }
    return 0;
}

void init_queue(LIST* queue){
    queue->size = 0;
    queue->head = NULL;
    queue->tail = NULL;
}

int destroy_queue(LIST* queue){
    NODE* delNode = NULL;
    while(queue->size){
        delNode = queue->head;
        queue->head = queue->head->next;
        queue->size--;
        free(delNode);
    }
    return 0;
}

int enqueue(LIST* queue, int data){
    NODE* newNode = NULL;
    newNode = (NODE*)malloc(sizeof(NODE));
    if(newNode == NULL){
        return -1;
    }
    newNode->data = data;
    newNode->next = NULL;
    if(0 == queue->size){
        queue->head = newNode;
        queue->tail = newNode;
    }
    else{
        queue->tail->next = newNode;
        queue->tail = newNode;
    }
    queue->size++;
    return 0;
}

int dequeue(LIST* queue, int* data){
    NODE* delNode = NULL;
    if(0 == queue->size){
        return -1;
    }
    delNode = queue->head;
    queue->head = queue->head->next;
    *data = delNode->data;
    free(delNode);
    queue->size--;
    return 0;
}


    8년 전
2개의 댓글이 있습니다.
  • seico75
    seico75

    그냥 k 받은 후에 k+1 크기의 원형큐를 만드시는 것이 가장 효율적이지 않을까요? 알고리즘 문제에서는 저 정도 크기는 그냥 통채로 잡는 것이 맞아 보입니다.


    8년 전 link
  • yhtgogo
    yhtgogo

    @seico75 네. 고맙습니다. 정말 님말씀처럼 원형큐가 딱 적당할 것 같아서 해보니 잘 해결할 수 있었습니다. ㅎㅎㅎㅎ
    한편으로는 동적 메모리 컨트롤을 해보니 시간이 많이 걸리기는 하네요.
    실전에서 메모리 컨트롤 잘 하시는 분들께 존경하는 마음이 솟구칩니다.


    8년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.