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

문제 링크: programmers.co.kr/learn/courses/30/lessons/64065

코딩테스트 연습 - 튜플

1. 주의할 점

- 각 원소를 모두 숫자로 끊는다. 이때, 2자리수 이상을 어떻게 처리해야 하는지 생각한다

 

2. 구현

- 문자열 S에서 문자 1개씩 읽는다. 이때, 숫자형태인 문자라면 str에 더한다. 아닌 경우, str을 int로 바꾼 이후, 0이 아니라면(""->0으로 치환된다. 또한, 자연수라고 했으므로 0이 나올 수 없다) Map에 해당 숫자가 나타난 횟수+1을 한다

- Map<>을 통해 <숫자, 해당 숫자가 나타난 횟수> 형태로 저장한다

- S를 모두 탐색했다면, 우선순위큐에 Map에 있는 원소를 넣는다. 이때, 정렬의 기준은 해당 숫자가 나타난 횟수에 대한 내림차순으로 정렬되도록 넣는다

- 우선순위큐에서 1개씩 뽑으면서 Answer에 넣는다

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <stdlib.h>
using namespace std;
struct info{
    int idx,val;
};
struct cmp{
    bool operator()(info &a, info &b){
        return a.val < b.val;
    }
};
info tmp;
map<int,int> m;     //숫자, 나온 횟수
priority_queue<info,vector<info>,cmp> pq;

vector<int> solution(string s) {
    vector<int> answer;
    string str="";
    for(int i=1;i<s.size()-1;i++){
        char c = s[i];
        if('0'<=c && c<='9') str+=c;
        else{
            int num = atoi(str.c_str());
            if(num!=0){
                if(m[num]==0) m[num]=1;
                else m[num] = m[num]+1;
            }
            str="";
        }       
    }
    for(auto it = m.begin();it!=m.end();it++){
        tmp.val = it->second;
        tmp.idx = it->first;
        pq.push(tmp);
    }
    while(!pq.empty()){
        answer.push_back(pq.top().idx);
        pq.pop();
    }
    return answer;
}