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

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

프로그래머스

먼저 깔끔한 문제풀이 설명은 카카오 테크 블로그에서 볼 수 있다.

https://tech.kakao.com/2020/04/01/2019-internship-test/

 

 

 

튜플이 (2, 1, 3)인 경우 문제 조건에 따라 집합으로 표현하면 다음과 같이 된다.

{{2}, {2, 1}, {2, 1, 3}} 

또한, 문제에서도 나와 있듯이 집합의 원소는 순서가 바뀌어도 상관없으므로

{{1,2}, {3, 1, 2}, {2}} 와 같이 표현해도 튜플 (2, 1, 3)을 나타낸다.

하지만 집합으로부터 튜플을 찾기 위해서는 {{2}, {2, 1}, {2, 1, 3}} 와 같이 원소의 개수가 작은 순으로 정렬되어 있어야 한다.

 

 

 

1. 우선 집합이 문자열로 주어지므로 파싱해서 같은 원소끼리 벡터에 넣어준다.

위의 {{1,2}, {3, 1, 2}, {2}} 로 예시를 들면, 원소들을 넣은 벡터를 다시 벡터에 넣어줘서

아래와 같이 2차원 벡터가 되도록 만들어준다.

vector<vector<char>> tmp = {{1,2}, {3, 1, 2}, {2}};

c++로 하다 보니까 문자열 파싱이 조금 번거롭긴 하지만 { 와 }, 쉼표( , ) , 숫자를 각각 구분해주면 된다.

숫자는 110처럼 한 자릿수가 아닐 수도 있으므로 쉼표가 나오기 전까지 하나의 숫자로 만들어주어야 한다. (이전의 수에 곱하기 10을 하고 현재수를 더해준다)

{ 인 경우는 따로 의미가 없어서 그냥 continue로 넘어가 주고

} 인 경우에 하나의 원소가 끝난 것이므로 벡터에 원소를 넣어주고 원소들을 넣어줬던 벡터를 다시 2차원 벡터에 넣어준다. 이때, 나중에 크기 순으로 정렬하기 위해서 원소들을 넣어줬던 벡터의 사이즈와 벡터를 함께 pair로 넣어준다.

vector < pair<int, vector<int> > > vt;

pair를 사용하면 정렬했을 때 pair의 첫 번째 값을 기준으로 먼저 정렬되기 때문에 이렇게 구현했지만, 크기를 기준으로 정렬하는 compare함수를 구현해서 정렬할 때 넣어줘도 된다.

 

 

 

2. 위에서도 언급했지만 순서가 섞여있는 집합을 {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4},... {a1, a2, a3, a4,..., an}}의 순서로 만들어 주어야 (a1, a2, a3, ..., an)의 튜플을 나타내는 원소를 쉽게 찾을 수 있는데, 그러기 위해서는 크기(원소가 들어가 있는 개수)를 기준으로 정렬해주면 된다.

위의 {{1,2}, {3, 1, 2}, {2}} 로 예시를 들면 크기로 정렬했을 때, {{2}, {2, 1}, {2, 1, 3}} 가 된다.

({2}는 1개이므로 크기가 1, {2, 1}은 2개이므로 크기가 2)

 

 

 

3. 마지막으로는 set을 이용하여 중복 체크를 해줬다. 벡터를 탐색하며 set에 없다면 set에 추가하고 answer에도 추가해줘서 튜플의 원소로 추가해준다.

 

#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
 
vector<int> solution(string s) {
    vector<int> answer;
 
    vector<int> tmp;
    vector < pair<int, vector<int> > > vt;
 
    int size = s.size();
    int num = 0;
 
//양끝 괄호는 무시하고 시작
    for (int i = 1; i < size - 1; i++) {
        if (s[i] == '{') continue;
 
        if (s[i] == '}') {
            tmp.push_back(num);
 
            //원소를 넣어줬던 tmp벡터를 vt벡터에 tmp벡터의 크기와 pair로 같이 넣어준다.
            vt.push_back(make_pair(tmp.size(), tmp));
            
            //num은 0으로 초기화하고 다음 원소를 넣어주기 위해 tmp벡터도 초기화
            num = 0;
            tmp.clear();
        }
        else if (s[i] == ',') {
            if (s[i - 1] == '}') continue; //이전 원소와 구분하는 쉼표라면 넘어간다.
            
            //숫자가 만들어졌으므로 벡터에 넣어주고 num은 0으로 초기화
            tmp.push_back(num);
            num = 0;
        }
        else {
            //원소(숫자)인 경우
            num *= 10;
            num += (s[i] - '0');
        }
    }
 
    sort(vt.begin(), vt.end());
 
    set<int> res;
    for (pair<int, vector<int>> p : vt) {
        //p.first: 벡터 크기, p.second: 원소 값
        for (int num : p.second) {
            //원소가 중복되지 않는다면 set에 추가해주고, answer 벡터에도 추가해준다.
            if (res.find(num) == res.end()) {
                res.insert(num);
                answer.push_back(num);
            }
        }
    }
 
 
    return answer;
}