[프로그래머스 LV2] 튜플 (문자열) / 2019 카카오 개발자 겨울 인턴십) [C++]

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

코딩테스트 연습 - 튜플

 

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

• {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}

--------------------------------------------------------

이 조건을 잘 이해해야 한다. 튜플은 1, 2, 3과 2, 1, 3이 다르므로 최종 결과 튜플의 순서를 잘 정하는 것이 중요하다.

튜플 a, b, c, d를 표현하려면 {a}, {b, a}, {c, a, b}, {d, a, b, c}도 된다는 것이다.

(집합의 원소의 순서는 바뀌어도 된다. 그 대신 집합 사이즈 1은 무조건 튜플의 첫 번째 원소여야 하고, 집합 사이즈 2는 무조건 튜플의 첫 번째 원소와 두 번째 원소로 이루어져야 한다)

 

따라서 집합 사이즈 1의 원소가 튜플의 첫 번째 원소가 되고, 사이즈 2의 원소들 중 1에서 찾은 원소를 뺀 나머지 원소가 두 번째 원소이므로 순서대로 집합 안에서 찾아야 한다.

 

1. 매 집합에서 찾은 튜플의 원소를 삭제하는 방법 +문자열 연습 버전

 - {a}, {b, a}, {c, a, b}, {d, a, b, c}에서 a를 찾으면 나머지 집합에서 a를 삭제

 - 0, {b}, {c, b}, {d, b, c}에서 그다음 b를 찾고 b를 삭제

이런 식으로 찾으면 튜플의 순서대로 구할 수 있다.

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

using namespace std;

bool compare(vector<string>& s1, vector<string>& s2) {
    return s1.size() < s2.size();
}

vector<int> solution(string s) {
    vector<int> answer;
    vector<vector<string>> list;
    s.erase(s.size() - 1, s.size());
    istringstream ss(s);
    string buffer = "";
    while (getline(ss, buffer, '}')) {
        vector<string> temp;
        string tempString = "";
        string subBuffer = buffer.substr(2);
        for (int i = 0; i < subBuffer.size(); i++) {
            if (isdigit(subBuffer[i])) {
                tempString += subBuffer[i];
            }
            else if (subBuffer[i] == ',') {
                temp.push_back(tempString);
                tempString = "";
            }
        }
        if (tempString.size())
            temp.push_back(tempString);
        list.push_back(temp);
    }

    sort(list.begin(), list.end(), compare);

    for (int i = 0; i < list.size(); i++) {
        answer.push_back(stoi(list[i][0]));
        for (int j = i + 1; j < list.size(); j++) {
            auto it = find(list[j].begin(), list[j].end(), list[i][0]);
            int index = it - list[j].begin();
            list[j].erase(list[j].begin() + index);
        }
    }

    return answer;
}

 

2. 집합 안의 숫자의 개수를 세서 튜플을 구성하는 방법

- 따지고 보면 제일 첫 번째 원소는 모든 집합에 포함되어 있고, 두 번째 원소는 두 번째 집합부터 끝까지 포함되어 있다.

따라서 나온 숫자의 개수를 세줘서 내림차순을 하면 그것이 바로 튜플의 순서이다.

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

using namespace std;

unordered_map<string, int> m;

vector<int> solution(string s) {
    vector<int> answer;
    string temp = "";
    for(auto c : s){
        if(c-'0' >= 0 && c-'0' <= 9){
            temp += c;
        }
        else{
            if(temp.size()){
                m[temp]++;
                temp.clear();
            }
        }
    }
    
    vector<pair<int, int>> v;
    
    for(auto it : m){
        v.push_back(make_pair(it.second, stoi(it.first)));    
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    for(int i = 0 ; i < v.size() ; i++){
        answer.push_back(v[i].second);
    }
    
    return answer;
}

map에 개수를 저장해주고, vector에 담아서 개수로 내림차순 정렬을 해주고 순서대로 튜플에 넣어준다.

 

최근 코테를 보면서 자주 나왔던 문자열 + 알고리즘 문제인 것 같다.