[HackerRank] Array Manipulation

https://www.hackerrank.com/challenges/crush/problem

Array Manipulation | HackerRank

문제 풀이)

 

    문제에 주어진대로 쿼리문을 실행하여 배열에 값들을 더해주고, 최대값을 찾아가는 연산은 시간초과가 난다.

 

    20만개의 쿼리문, 그리고 최대 1000만개까지 데이터가 존재하고 a와 b도 1부터 n까지 가능하므로 최악의 경우

 

    20만 x 1000만 만큼의 for문이 돌아간다. 당연히 시간초과가 날 수밖에 없다.

 

    이러한 문제를 쿼리문의 개수(최대 20만) + 데이터의 개수(1000만) 으로 줄일 수 있는 방법이 있다.

 

    문제에서 a ~ b의 범위 안에 k만큼을 모두 더해주라고 하고 있지만, 이를 인덱스 a에는 k를 더해 저장하고,

 

    인덱스 b + 1에는 k를 뺀 값을 저장해주는 것이다. 즉 a에는 k, b + 1에는 -k 가 더해진 채로 존재하고,

 

    a + 1 ~ b 까지는 아무 값도 존재하지 않는 형태이다.

 

    이 후에 데이터의 개수만큼 진행하면서 새로운 long 변수에 값을 더해주면서 최대 값을 갱신해주면 된다.

 

 

    주의) long은 비주얼에서 int와 같이 4byte로 사용되었으나 hackerRank의 환경에서는 8byte 이상으로 보인다.

 

< 소스 코드 >

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// Complete the arrayManipulation function below.
long arrayManipulation(int n, vector<vector<int>> queries) {

    vector<long> result(n + 1);
    for(int i = 0; i < queries.size(); ++i)
    {
        long a = queries[i][0];
        long b = queries[i][1];
        long k = queries[i][2];

        result[a - 1] += k;
        result[b] -= k;
    }

    long nMax = 0;
    long nTmp = 0;
    for(int i = 0 ; i < n; ++i)
    {
        nTmp += result[i];
        if(nMax < nTmp) nMax = nTmp;
    }
    return nMax;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string nm_temp;
    getline(cin, nm_temp);

    vector<string> nm = split_string(nm_temp);

    int n = stoi(nm[0]);

    int m = stoi(nm[1]);

    vector<vector<int>> queries(m);
    for (int i = 0; i < m; i++) {
        queries[i].resize(3);

        for (int j = 0; j < 3; j++) {
            cin >> queries[i][j];
        }

        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }

    long result = arrayManipulation(n, queries);

    fout << result << "\n";

    fout.close();

    return 0;
}

vector<string> split_string(string input_string) {
    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
        return x == y and x == ' ';
    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {
        input_string.pop_back();
    }

    vector<string> splits;
    char delimiter = ' ';

    size_t i = 0;
    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {
        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;
        pos = input_string.find(delimiter, i);
    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;
}