[프로그래머스 / C++] 튜플

문제

튜플 : 문제 링크

문제 분석

• 셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 한다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있다.

• (a1, a2, a3, ..., an)

• 튜플은 다음과 같은 성질을 가지고 있다.

1. 중복된 원소가 있을 수 있다. ex : (2, 3, 1, 2)
2. 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플이다. ex : (1, 2, 3) ≠ (1, 3, 2)
3. 튜플의 원소 개수는 유한한다.

• 원소의 개수가 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}}

• 와 같이 표현할 수 있다. 이때, 집합은 원소의 순서가 바뀌어도 상관없으므로

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}
• {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}
• {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}

• 는 모두 같은 튜플 (2, 1, 3, 4)를 나타낸다. 특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성

• 제한 사항

• s의 길이는 5 이상 1,000,000 이하이다.
• s는 숫자와 '{', '}', ',' 로만 이루어져 있다.
• 숫자가 0으로 시작하는 경우는 없다.
• s는 항상 중복되는 원소가 없는 튜플을 올바르게 표현하고 있다.
• s가 표현하는 튜플의 원소는 1 이상 100,000 이하인 자연수이다.
• return 하는 배열의 길이가 1 이상 500 이하인 경우만 입력으로 주어진다.

• 해시 맵인 unorderd_map을 사용할 것 이므로 unorderd_map 헤더를 include
• 벡터의 내림차순 정렬을 위해 sort() 함수를 사용할 것 이므로 algorithm 헤더를 include
• 키는 숫자, 값은 해당 숫자의 빈도를 저장할 unorderd_map m을 초기화. 문자열 s가 표현하는 튜플을 저장할 정수형 벡터 answer을 초기화
• for loop의 처음과 마지막 괄호는 순회가 불필요하므로 초기화 식을 i = 2, 조건식을 i < s.size() - 2로 설정. if문을 사용하여 s의 현재 인덱스 원소가 숫자 형태일경우, stoi() 함수와 substr() 함수를 사용하여 현재 인덱스에서 시작하는 숫자를 정수로 변환하여 해시 맵에 추가하거나 빈도수를 증가시킴. 이후, while loop를 사용하여 두 자리 이상의 숫자를 처리하기위해 i를 숫자가 끝나는 위치로 이동시킴.
• loop 탈출 후, pair형 벡터 mtov에 해시 맵의 모든 원소의 숫자와 빈도수로 이후어진 쌍을 복사. sort() 함수를 사용하여 빈도수에 따라 내림차순으로 정렬. for loop를 통해 정렬된 mtov의 첫번째부터 마지막 원소까지 순회하고, pair중 숫자에 해당하는 first를 answer에 순서대로 저장. 최종적으로 저장된 answer을 return

algorithm 헤더의 sort() 함수 사용법
void sort(T start, T end, Compare comp); //comp 인자가 공란이면 오름차순 정렬

• sort(v.begin(), v.end(), compare); // 사용자 정의 함수 사용
• sort(v.rbegin(), v.rend()); // 내림차순
• sort(v.begin(), v.end(), greater<자료형>()); // 내림차순
• sort(v.begin(), v.end(), less<자료형>()); // 오름차순

unordered_map
map의 해시 테이블 버전이다. <unordered_map> 헤더에 다음과 같이 정의되어 있다.

template<
	typename _Kty,
    typename _Ty,
    typename _Hasher = std::hash<_Kty>,
    typename _Keyeq = std::equal_to<_Kty>,
    typename _Alloc = std::allocator<std::pair<const _Kty, _Ty>>
class unordered_set;

map의 인터페이스를 모두 포함하고 있으며 추가적으로 HashTable 관련 인터페이스들을 제공한다.

풀이

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<int> solution(string s) {
    unordered_map<int, int> m;
    vector<int> answer;
    
    for(int i = 2; i < s.size() - 2; ++i) {
        if('0' <= s[i] && s[i] <= '9') {
            m[stoi(s.substr(i))]++;
            while('0' <= s[i] && s[i] <= '9') i++;
        }
    }
    vector<pair<int, int>> mtov(m.begin(), m.end());
    sort(mtov.begin(), mtov.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second;
    });
    for(int i = 0; i < mtov.size(); ++i) answer.push_back(mtov[i].first);
    return answer;
}