DOLLS RTE 질문드립니다.

  • gandhihb
    gandhihb

    안녕하세요? 최근에 가입하여 JMBook 보면서 이문제 저문제 풀고있는 초보입니다.

    DOLLS 에서 RTE (SIGSEGV: segmentation fault, probably incorrect memory access or stack overflow)가 났는데, 해결이 요원하여 질문글을 올립니다.

    우선, 문제를 해결하려고 접근한 방식은 아래와 같습니다.

    1. 가장 적은 갯수의 인형 종류를 찾고,
    2. 그 인형의 갯수* 남은 인형 종류 <= 구해야할 전체 갯수이면,
    3. 남아있는 전체 인형 종류를 돌면서 1에서 구한 갯수만큼 빼고
    4. 해당 갯수만큼 카운터를 올려준다.
    5. 1에서 찾은 가장 적은 갯수의 인형 종류는 아예 빼버린다.
    6. 위 과정을 반복하다 2가 아니면,
    7. 남아있는 인형들을 하나씩 종류별로 순서대로 카운팅 해주다가
    8. 구해야할 갯수가 되면 멈추고 카운팅 된 갯수들을 출력한다.

    메모리를 깨먹을 법한 부분은 없어보이는데.. 아니면 stack overflow라면, 다른 메모리를 더 적게 쓰는 자료구조형을 이용하도록 고민해야할까요?

    아래는 코드입니다.

    #include <iomanip>
    #include <cstdio>
    #include <algorithm>
    #include <iostream>
    #include <vector>
    #include <set>
    #include <map>
    #include <queue>
    #include <utility>
    #include <string>
    using namespace std;
    int T, n, m;
    int doll, cnt;
    bool byIndex(pair<int, int> a, pair<int, int> b)
    {
        return a.second < b.second;
    }
    int main()
    {
        freopen("sample_input.txt", "r", stdin);
        cin >> T;
        while (T--)
        {
            scanf("%d %d", &n, &m);
            //인형을 갯수/인덱스 순서로 deque에 저장
            deque<pair<int, int> > dolls;
            vector<int> selected;
            selected.resize(n,0);
            for (int i = 0; i < n; i++)
            {
                scanf("%d", &doll);
                dolls.push_back(make_pair(doll, i));
            }
    
            //인형을 갯수의 오름차순으로 정렬
            sort(dolls.begin(), dolls.end());
            int remain = m;
            int remain_type = n;
            while (remain >= dolls[0].first*dolls.size())
            {
                int current_quantity = dolls[0].first;
                remain -= current_quantity * dolls.size();
                for (deque<pair<int,int> >::iterator it = dolls.begin(); it != dolls.end(); it++)
                {
                    selected[(*it).second] += current_quantity;
                    (*it).first -= current_quantity;
                }
                dolls.pop_front();
            }
    
            //남아있는 인형들을 인덱스의 오름차순으로 정렬
            sort(dolls.begin(), dolls.end(), byIndex);
            deque<pair<int, int> >::iterator iter = dolls.begin();
            while (remain && !dolls.empty())
            {
                selected[(*iter).second]++;
                (*iter).first--;
                iter++;
                if (iter == dolls.end())
                    iter = dolls.begin();
                remain--;
            }
            for (vector<int>::iterator it = selected.begin(); it != selected.end(); it++)
            {
                printf("%d ", *it);
            }
            printf("\n");
        }
    
        return 0;
    }
    

    조언 부탁드립니다. 감사합니다.


    2년 전
2개의 댓글이 있습니다.
  • 일루
    일루

    2-4 과정을 n번 반복하고 나서 다시 2번으로 가면 RTE가 날 것 같습니다.

    사실 그걸 고쳐도 알고리즘이 비효율적이라 TLE가 나야 할 것 같습니다. 안 난다면 데이터가 약한거니 연락해주세요~


    2년 전 link
  • gandhihb
    gandhihb

    답변 감사합니다. 해당 부분 고쳐서 TLE 나는것 확인했습니다 ㅠ.ㅠ
    좀 더 고민해서 다른 방법으로 구현해볼께요~


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