글 읽기 - 자꾸 메모리 초과가 나오네요... 조언 부탁드립니다

uuiip7878 2년 전 0

var 배열에 중복되지 않게 각 원소를 하나씩만 넣어주고 각 숫자의 count를 센 뒤 이분탐색을 이용해서 target + n(n>1)이 있는지 없는지 검사해서 switch 문으로 구분시켜서 답을 구하는 식으로 짰는데 메모리 초과가 자꾸 뜨네요...ㅠㅠ 혹시 원인을 아실 것 같은 분은 댓글로 부디 조언 부탁드립니다.

#include <bits/stdc++.h>
std::vector<int> var;
bool check(const int target, int p){
    return target+1<var[p];
}
int bsf(const int target, int high, int low){//target+n = target+n(n>1)이 있음 1 = target+n(n>1)이 없음
    if(low+1>=high)return check(target,low)?var[low]:check(target,high)?var[high]:1;
    int mid=(low+high)/2;
    if(check(target,mid)==check(target,low))low=mid;
    else if(check(target,mid)==check(target,high))high=mid;
    bsf(target,high,low);
}

int c[1001];
int arr[51];
int main(){
    int a;
    scanf("%d",&a);
    for(int i=0;i<a;i++){
        scanf("%d",&arr[i]);
    }
    std::sort(arr,arr+a);
    int cc=0;
    for(int i=0;i<a;i++){
        cc++;
        if(arr[i]!=arr[i+1] || i+1==a){
            var.push_back(arr[i]);
            c[arr[i]]=cc;
            cc=0;
        }
    }
    int s = var.size();
    for(int i=0;i<s;i++){
        int res = bsf(var[i],var.size()-1,i);
        if(var[i+1]!=var[i]+1 || i+1==s)res=0;
        switch(res){
        case 0:
            for(int j=0;j<c[var[i]];j++)printf("%d ",var[i]);
            break;
        case 1:
            for(int j=0;j<c[var[i+1]];j++)printf("%d ",var[i+1]);
            for(int j=0;j<c[var[i]];j++)printf("%d ",var[i]);
            var.erase(var.begin()+i+1);
            s--;
            break;
        default:
            for(int j=0;j<c[var[i]];j++)printf("%d ",var[i]);
            printf("%d ",res);
            c[res]--;
            int t = std::upper_bound(var.begin(),var.end(),res)- var.begin();
            if(c[res]==0){var.erase(var.begin()+t-1);s--;}
        }
    }
}

uuiip7878 2년 전 0

아무래도 재귀함수에서 계속 메모리를 복사해가는게 원인 같아서 비재귀적으로 코드를 수정하고 올려서 해결했습니다.

uuiip7878 2년 전 0

이제 보니 제가 return 문을 마지막에 추가를 안 해서 undefined behavior가 발생한 것 같네요;

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

문제

문제

출처

ICPC

자꾸 메모리 초과가 나오네요... 조언 부탁드립니다

uuiip7878 2년 전 0

uuiip7878 2년 전 0

uuiip7878 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말