Question

test 8쯤 부터 3000ms 이상 걸리는 경우(정답 코드 o)

분명히 코드는 맞는데 시간초과가 이상하게 떠서 몇 시간을 고생 했는데 매개변수로 넘길때 map이나 vector같은 큰 메모리를 차지하는 것들은 재귀함수로 풀때 매번 복사해서 넘기느냐 아니면 참조 매개변수로 복사 없이 주솟값만 넘기느냐가 엄청 큰 걸 알았네요.

dfs의 매개변수로 들어오는 mpIndex를
& mpIndex 로 받느냐
mpIndex 로 받느냐에 따라
&하나 차이로 당락이 결정됩니다!

다른 vector들은 const나 &도 다 붙였으면서 map은 실수로 & 하나 안 붙였더니 시간 초과 뜨고...
덕분에 앞으로는 이렇게 안틀리겠죠!

아래 코드는 시간초과 뜨는 코드이고 mpIndex를 참조 매개변수로 받기위해 &하나만 붙이면 통과합니다

작성중인 코드―solution.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

void dfs(int idx, const vector<string>& referral, unordered_map<string, int> mpIndex, int profit, vector<int>& answer) 
{
    if (profit == 0) return;
    int share = profit / 10;
    answer[idx] += profit - share;
    if (referral[idx] != "-" && share > 0) {
        dfs(mpIndex[referral[idx]], referral, mpIndex, share, answer);
    }
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer(enroll.size(),0);
    unordered_map<string,int> mpIndex;

    for(int i=0;i<enroll.size();i++){
        mpIndex[enroll[i]] = i;        
    }

    for(int i=0;i<seller.size();i++)
    {
        int idx = mpIndex[seller[i]];
        int profit = amount[i]*100;
        dfs(idx, referral, mpIndex, profit, answer);

    }

    return answer;
}

최재우

2025.1.12 12:06

test 8쯤 부터 3000ms 이상 걸리는 경우(정답 코드 o)

작성중인 코드―solution.cpp

0 개의 답변

답변 쓰기

이 입력폼은 마크다운 문법을 지원합니다.