[HackerRank] Picking Numbers

HackerRank 알고리즘 문제 풀이

분류

Practice > Algorithms > Implementation

문제 링크 : https://www.hackerrank.com/challenges/picking-numbers/problem

풀이

• n개의 리스트에서 숫자를 뽑는다.

• 뽑은 숫자들의 절댓값이 1 이하인 수들로 subarray를 구성시킬 때, 가장 긴 subarray의 길이를 반환한다.

• 우선 2개의 수 base_1과 base_2를 뽑고, 두 수의 차이의 절댓값이 1이하인 경우에만 수를 뽑아나간다. (이때, 숫자는 최소 2개를 뽑고 시작해야 하므로, tempLength의 초기값은 1이다.)
• abs(base_1 - a[k]) <= diff && abs(base_2 - a[k]) <= diff && abs(a[i] - a[k]) <= diff) 이 조건을 만족시키는 경우에만 숫자를 뽑을 수 있고, 뽑을 수 있는 경우에는 tempLength 값을 1씩 증가시킨다.
• 이렇게 한 번의 사이클이 끝나면 maxLength 값을 최댓값으로 갱신한다.

---

일반적인 구현(Implementation) 문제인데 다른 유형의 문제를 많이 풀어서 그런지 구현 문제에 대한 감이 약간 낮아진 것 같다. (그래프 문제가 더 편하게 느껴질 정도.) 이러한 구현 문제의 경우 입력으로 주어지는 n값이 작아도 모든 경우의 수를 확인하기 위한 반복 과정으로 풀리는 경우가 제법 있는데, 언제부터인가 ‘문제에 어떤 함정이 있을까?’라는 생각을 하게 되어 시간이 더 소요되고 있다. 다양한 문제에 감을 되찾는 것이 중요할 것 같다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);

/*
 * Complete the 'pickingNumbers' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts INTEGER_ARRAY a as parameter.
 */

 // 1 2 2 3 1 2
int pickingNumbers(vector<int> a) {
    int maxLength = 0;
    for (int i = 0; i < (int)a.size() - 1; ++i) {
        int base_1 = a[i], base_2;
        for (int j = i + 1; j < (int)a.size(); ++j) {
            base_2 = a[j];
            int diff = abs(base_1 - base_2);
            if (diff > 1) continue;

            int tempLength = 1;
            for (int k = i + 1; k < (int)a.size(); ++k) {
                if (abs(base_1 - a[k]) <= diff && abs(base_2 - a[k]) <= diff
                    && abs(a[i] - a[k]) <= diff) {
                    ++tempLength;
                }
            }
            if (maxLength < tempLength) {
                maxLength = tempLength;
            }
        }
    }
    return maxLength;
}

int main()
{
    string n_temp;
    getline(cin, n_temp);

    int n = stoi(ltrim(rtrim(n_temp)));

    string a_temp_temp;
    getline(cin, a_temp_temp);

    vector<string> a_temp = split(rtrim(a_temp_temp));

    vector<int> a(n);

    for (int i = 0; i < n; i++) {
        int a_item = stoi(a_temp[i]);

        a[i] = a_item;
    }

    int result = pickingNumbers(a);

    cout << result << "\n";

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

vector<string> split(const string &str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}