글 읽기 - [C] 메모리 초과 관련 질문입니다

qndbswhd1 2년 전 0

예제와 다른 반례를 입력했을 때 맞게 출력이 되어 제출했지만 '메모리 초과'가 발생하여 질문드립니다..

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

typedef struct _QueueNode{
    struct _QueueNode* next;
    int value;
} QueueNode;

typedef struct _QueueList{
    QueueNode* front;
    QueueNode* back;
    int size;
} QueueList;

void push(QueueList* queue, int val);
int pop(QueueList* queue);
void solve_josephus(QueueList* queue, int interval);

int main(){
    int num, interval;
    scanf("%d %d", &num, &interval);

    QueueList* Queue = calloc(1, sizeof(QueueList));
    for(int i = 1; i <= num; i++){
        push(Queue, i);
    }

    solve_josephus(Queue, interval);

    free(Queue);
    return 0;
}

void push(QueueList* queue, int val){
    QueueNode* new = malloc(sizeof(QueueNode));
    new->next = NULL;
    new->value = val;
    if(queue->size == 0){
        queue->front = new;
        queue->back = new;
    }
    else{
        queue->back->next = new;
        queue->back = new;
    }
    queue->size++;
}

int pop(QueueList* queue){
    if(queue->size == 0)    return -1;
    else{
        int ret = queue->front->value;
        queue->front = queue->front->next;
        queue->size--;
        return ret;
    }
}

void solve_josephus(QueueList* queue, int interval){
    int idx = 1, to_move;
    printf("<");
    while(queue->size != 0){
        if(idx % interval != 0){
            to_move = pop(queue);
            push(queue, to_move);
        }
        else{
            if(queue->size == 1)    printf("%d", pop(queue));
            else    printf("%d, ", pop(queue));
        }
        idx++;
    }
    printf(">");
}

djm03178 2년 전 1

push를 할 때마다 malloc을 수행하고 있는 것처럼, 반대로 pop을 할 때마다 pop된 노드에 대한 free가 바로바로 이루어져야 합니다.

이 풀이 방식은 O(N^2)에 동작하는데, 노드 하나 하나의 크기가 상당히 크기 때문에 문제에 주어진 256MB 제한을 넘을 수 있어 보입니다.

qndbswhd1 2년 전 0

감사합니다! 아래 코드처럼 수정하여 해결하였습니다!!

int pop(QueueList* queue){
    if(queue->size == 0)    return -1;
    else{
        QueueNode* temp = queue->front;
        int ret = temp->value;
        queue->front = temp->next;
        queue->size--;
        free(temp);
        return ret;
    }
}

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

문제

문제

출처

ICPC

[C] 메모리 초과 관련 질문입니다

qndbswhd1 2년 전 0

djm03178 2년 전 1

qndbswhd1 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말