[2019 카카오 개발자 겨울 인턴십] 튜플(C++)

튜플

코딩테스트 연습 - 튜플

 

문제 설명

 

 - 원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., 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}}이다.

 

 - 특정 튜플을 표현하는 집합이 담긴 문자열 s가 주어질 때, s가 표현하는 튜플을 배열에 담아 반환하라.

---

 

입력 값

 

 - 튜플을 표현하는 집합 문자열 s의 길이는 5이상 1,000,000 이하이다.

 

 - s는 숫자와 '{', '}', ',' 로만 이루어져 있다.

 

 - 숫자가 0으로 시작되는 경우는 없다.

 

 - s는 항상 중복 원소가 없는 튜플을 올바르게 표현하고 있다.

 

 - s가 표현하는 튜플의 원소는 1이상 100,000 이하인 자연수이다.

 

 - return 하는 배열의 길이가 1이상 500이하인 경우에만 입력으로 주어진다.

 

---

 

예제

---

 

문제 분석

 

 - 문자열을 파싱하여, 원소가 되는 값들을 추출해야 한다.

 

 - 튜플의 길이가 n개인 경우 맨 처음 원소는 n개가 등장하고, 두 번째 원소는 n-1개, ... 마지막 원소는 1개가 등장한다.

   ( 튜플 (2, 1, 3, 4) 인 경우 2가 4개, 1이 3개, 3이 2개, 4가 1개 등장.)

 

 - 각 원소가 몇 번 등장하는지 파악하고, 해당 원소를 등장 횟수를 바탕으로 내림차순으로 정렬하면 된다.

 

---

 

소스 코드

#include <bits/stdc++.h>
#include <unordered_map>
#include <string>

using namespace std;

vector<int> solution(string s) {
    vector<int> answer;
    unordered_map<int,int> um;
    string number="";
    
    for(auto c : s)
    {
        if(c=='{' || c=='}')
            continue;
        else if(c==',')
        {
            um[stoi(number)]++;
            number="";
        }
        else
            number+=c;
    }
    um[stoi(number)]++;
    
    answer=vector<int>(um.size(),0);
    
    for (auto u : um)
	{
		answer[um.size()-u.second]=u.first;
	}
    
    
    return answer;
}