[2019 카카오 인턴] 튜플 (C++)

 

2019 카카오 인턴 코테 문제

5시간을 잡고 실전처럼 진행하였으며 코드의 최적화나 알고리즘은 정확하지 않음.

---

코딩테스트 연습 - 튜플 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 튜플

---

2단계치곤 쉬운문제였다. 약 30분정도 소요되었다.

문제의 답은 다음과 같이 구하면 된다.

원소 갯수가 1개짜리면 set에서 1번째, 2개짜리중 전체집합에 없는것이 set에서 2번째, ..... 하면 된다.

말로만봐선 이해하기 힘든데, 예시로 {a}, {b, a}, {c, b, a} 가 주어진다고 한다.

갯수가 1개짜리인 집합은 {a}  이고 이것이 전체 set에서 첫번째이므로 현재 전체 set은 {a} 이다. 

다음으로 2개짜리인 집합은 {b, a} 이며, 전체 집합에 없는것은 b이다.  따라서 전체집합은 {a, b} 가 된다.

마지막으로 3개짜리인 집합은 {c, b, a}이며, 전체집합에 없는것은 c이다. 따라서 전체집합은 {a, b, c}가 된다.

따라서 우리가 할 일은, string을 갯수에 따라 집합을 나눠 parsing하는 것이 다라고  볼 수 있다.

parsing은 { 이 들어온다면 } 이 나올때 까지 동일한 집합이며, 처음과 끝의 { } 를 빼고 생각한다면 쉽다.

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

using namespace std;

vector<int> solution(string s) {
    vector<int> answer;

    int cnt = 0;
    for (int i = 1; i < s.size() - 1; i++)
        if (s[i] == '{')
            cnt++;

    vector<vector<int>> set(cnt + 1);

    for (int i = 1; i < s.size() - 1; i++)
    {
        if (s[i] == '{')
        {
            i++;
            string num = "";
            vector<int> temp;
            while (i < s.size())
            {
                num += s[i];
                i++;
                if (s[i] == ',')
                {
                    temp.push_back(stoi(num));
                    num = "";
                    i++;
                }
                else if (s[i] == '}')
                {
                    temp.push_back(stoi(num));
                    break;
                }
            }
            
            set[temp.size()] = temp;
        }
    }

    for(int i = 1; i <= cnt; i++)
        for(int j = 0; j < set[i].size(); j++)
            if (find(answer.begin(), answer.end(), set[i][j]) == answer.end())
            {
                answer.push_back(set[i][j]);
                break;
            }

    return answer;
}