Level 2. 튜플

Level 2. 튜플

 

 

파싱하는 것이 주가 아닌 문제였는데 파싱조차 까다로운 문제였다.

1. 나는 일단 양 끝의 중괄호 2개씩을 제거하고 "},{"를 " " 공백으로 교체해 1번 파싱했다.
2. 그리고 콤마로 구분된 숫자 배열 문자열에서 "," 를 " " 공백으로 교체해 배열의 각 숫자 하나씩을 가져왔다.

 

2차원 벡터에 숫자들이 담기고 나서는 크기가 작은 벡터에 담긴 수일수록 앞에 온다는 성질을 이용해, 길이가 1인 벡터의 숫자를 정답에 추가하고 나머지 벡터에서 제거하는 방식으로 해결했다.

 

#include <iostream>
#include <vector>
#include <regex>
#include <sstream>
#include <algorithm>

using namespace std;

vector<int> solution(string s)
{
    vector<int> answer;
    vector<vector<int>> elements;
    string input;

    s = string(s.begin() + 2, s.end() - 2);
    s = regex_replace(s, regex("\\},\\{"), " ");

    istringstream iss(s);

    while (iss >> input)
    {
        replace(input.begin(), input.end(), ',', ' ');

        int num;
        istringstream iss2(input);

        elements.emplace_back(vector<int>());

        while (iss2 >> num)
            elements.back().emplace_back(num);
    }

    while (!elements.empty())
    {
        int num;
        vector<vector<int>>::iterator it;

        for (it = elements.begin(); it->size() != 1; ++it);
        num = it->front();

        answer.emplace_back(num);
        
        for (vector<int>& v : elements)
            v.erase(find(v.begin(), v.end(), num));
        elements.erase(it);
    }

    return answer;
}

 

다른 사람은 2차원 배열에 숫자들을 저장하지 않고 해결했다.

 

모든 원소에 등장하는 수를 커버할 만큼 큰 100,001 크기의 인덱스 배열을 만들고, 등장하는 수들은 값을 증가시킨다.

 

배열에서 0이 아닌 인덱스와 등장 횟수만 추출한 후, 등장 횟수를 기준으로 정렬해 해결했다.

 

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <string>

#define index(v, val) find((v).begin(), (v).end(), (val)) - (v).begin()

using namespace std;

vector<int> solution(string s)
{
    vector<int> answer;
    vector<int> counts;
    int* arr = new int[100'001]();
    string tmp;

    for (char c : s)
        if (isdigit(c))
            tmp += c;
        else if (0 < tmp.length())
            ++arr[stoi(tmp)],
            tmp.clear();

    for (int i = 0; i < 100'001; ++i)
        if (0 < arr[i])
            answer.emplace_back(i),
            counts.emplace_back(arr[i]);
    
    vector<int> t = answer;
    auto pred = [&](int a, int b) { return counts[index(t, a)] > counts[index(t, b)]; };
    sort(answer.begin(), answer.end(), pred);

    delete[] arr;
    arr = nullptr;

    return answer;
}

 

항상 느끼는 것이지만 정규 표현식 관련 함수는 시간을 너무 많이 잡아먹는 것 같다.

 

이번 풀이에서는 내 방식이 마지막에 O(n²)의 시간 복잡도를 갖기 때문에 오래 걸린 걸 수도 있다.

• v.erase(find())에서도 O(n)이 소요되니 어쩌면 O(n³)인지도 모르겠다. OTL

 

나의 풀이 (좌) / 다른 사람의 풀이 (우)