프로그래머스 2019 카카오 개발자 겨울 튜플 풀이

programmers.co.kr/learn/courses/30/lessons/64065

코딩테스트 연습 - 튜플

이 문제에서는 각 집합을 탐색하며 숫자인지를 판별하고 검색될 때마다 검색된 횟수를 1씩 올려주는 방식으로 풀이했다.

#include <string>
#include <vector>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
using namespace std;

bool cmp(pair<int,int> a, pair<int,int> b) { //sort 비교 함수
    return a.second > b.second; //검색횟수가 많은 순서대로 저장
}

vector<int> solution(string s) {
    vector<int> answer;
    char num[100001] = {0}; //숫자를 만들 배열
    vector<int> arr;
    vector<pair<int,int>> tmpans;
    bool visit[501]; //탐색한지 확인
    int cnt = 0;
    int idx = 0;
    for(int i = 0; i < s.length(); i++) {
            if(s[i] == '{') { //시작시 메모리 초기화
                idx = 0;
                memset(visit, 0, sizeof(visit));
                memset(num, 0, sizeof(num));
            }
            else if(s[i] == '}') {
                if(num[0] != 0) { //숫자생성
                    int n = atoi(num);
                    memset(num, 0, sizeof(num));
                    arr.push_back(n);
                    cnt++; //한 집합에서 숫자의 개수 추가
                }
                else {//입력의 마지막 '}'인 경우
                    continue;
                }
                if(arr.size() != 0) { //집합에 숫자가 있는 경우
                    if(cnt < tmpans.size()) { //만약 지금까지 탐색한 튜플의 원소가 더 많은 경우 검색횟수만 +1
                        for(int j = 0; j < tmpans.size(); j++) {
                            for(int k = 0; k < arr.size(); k++) {
                                if(tmpans[j].first == arr[k]) {
                                    tmpans[j].second++;
                                }
                            }
                        }
                    }
                    else { //새로운 튜플 원소가 나타난 경우
                        for(int j = 0; j < arr.size(); j++) {
                            int chk = 0;
                            int k;
                            for(k = 0; k < tmpans.size(); k++) {
                                if(visit[k]) { //탐색한 튜플 원소 건너뜀
                                    continue;
                                }
                                if(tmpans[k].first == arr[j]) { //이미 검색된 원소는 검색횟수 1추가
                                    tmpans[k].second++;
                                    visit[k] = 1;
                                    chk = 1;
                                    break;
                                }
                            }
                            if(!chk && (k == tmpans.size())) { //새로운 원소 추가하고 검색횟수 1로 설정
                                tmpans.push_back({arr[j], 1});
                            }
                        }
                    }
                    memset(visit, 0, sizeof(visit));
                }
                else continue;
                cnt = 0;
                arr.clear();
                idx = 0;
                memset(num, 0, sizeof(num));
            }
            else if(s[i] ==  ',') {
                if(num[0] != 0) { //집합을 구분 짓는 ','이 아닌 경우
                    int n = atoi(num);
                    arr.push_back(n);
                    memset(num, 0, sizeof(num));
                    cnt++;
                }
                memset(num, 0, sizeof(num));
                idx = 0;
                continue;
            }
            else { //10진수 숫자 생성
                num[idx++] = s[i];
            }
    }
    sort(tmpans.begin(), tmpans.end(), cmp); //검색 횟수 순으로 정렬
    for(int i = 0; i < tmpans.size(); i++) { //정답 옮겨 저장
        answer.push_back(tmpans[i].first); 
    }
    return answer;
}

임시 정답 vector를 선언하고 원소와 검색된 횟수를 저장한다. 모든 집합을 탐색하며 기존에 검색된 원소 수보다 많은 경우 모두 1씩 증가하고 없는 원소는 추가하여준다. 입력값을 모두 탐색한 후 가장 많은 빈도의 원소 순으로 정렬되므로 정답에는 원소만 옮겨 저장해준다.