[프로그래머스] level2 튜플 (C++)

2019 카카오 겨울 인턴십

 

 

배열이 주어지고, 튜플을 만드는 방법을 문제에서 친절히 알려줬다.

원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.
{{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}

예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는
{{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

 

 

문제에서 원하는 답은 튜플을 분석해서 원래의 배열을 구하라는 것이다.

문제는 튜플이 문자열로 주어진다는 것이다..

나는 C++로 풀어서 파싱하는 과정이 조금 귀찮았지만, 파이썬으로 풀면 전체 코드가 9-10줄 정도면 충분하다고 한다.

 

 

튜플 문자열 파싱

int number = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '{') continue;
        if(s[i] == '}' || s[i] == ','){
            num[number]++;
            number = 0;
            continue;
        }
        if(isdigit(s[i])){
            number = number * 10 + (s[i] - '0');
        }
    }

'{'는 넘어간다.

'}'이거나 ','인 경우에는 숫자가 끝났다는 의미이므로 지금까지 만든 숫자를 가지고 해당 숫자가 나온 횟수를 1 증가시킨다.

만약 현재 문자가 숫자로 변환 가능하다면 number = number*10 + (숫자) 식을 이용해서 숫자를 저장해둔다.

 

 

숫자의 최대 크기가 10만이다. 따라서 10만의 배열에 각 숫자가 몇 번 나왔는지 저장가능하다.

위 파싱 과정에서 저장이 완료되고

만들어진 배열을 돌면서 숫자가 나왔다면, 해당 숫자와 그 숫자가 몇 번 나왔는지를 pair로 묶어서 다른 벡터에 넣어준다.

 

튜플을 만드는 배열의 숫자는 왼쪽으로 갈 수록(인덱스가 0으로 갈수록) 숫자가 등장하는 횟수가 증가한다.

따라서 알맞게 정렬을 해준다면 답을 구할 수 있다.

 

#include <string>
#include <vector>
#include <cctype>
#include <algorithm>

using namespace std;

int num[100001];

vector<int> solution(string s) {
    vector<pair<int, int> > vec;
    vector<int> answer;
    
    int number = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '{') continue;
        if(s[i] == '}' || s[i] == ','){
            num[number]++;
            number = 0;
            continue;
        }
        if(isdigit(s[i])){
            number = number * 10 + (s[i] - '0');
        }
    }
    
    for(int i = 1; i < 100001; i++){
        if(!num[i]) continue;
        vec.push_back({num[i], i});
    }
    
    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());
    
    for(auto w: vec){
        answer.push_back(w.second);
    }
    
    return answer;
}