프로그래머스 튜플 C++

https://school.programmers.co.kr/learn/courses/30/lessons/64065?language=cpp 

프로그래머스

몇번의 시행착오를 겪었다. 처음에 내가 든 생각은 다음과 같다.

 

"{{2},{2,1},{2,1,3},{2,1,3,4}}"

 

1 먼저 문자열로 입력이 들어오는데, 괄호를 제외한 순수한 문자열을 얻는다.

(위의 경우 "2","21","213","2134"순으로 괄호를 제외해서 문자열을 얻는다)

 

2 문자열을 크기 순으로 정렬한다.

3 크기 순으로 정렬된 문자열이 있다면, 다음 크기의 문자열에서 기존 문자열을 찾아서 제거하고, 

남은 문자열을 정수로 바꾼다.

 

이러한 방법은 다음의 예제를 해결하지 못했다.

"{{4,2,3},{3},{2,3,4,1},{2,3}}"	[3, 2, 4, 1]

 

위의 방법대로 한다면 

먼저 문자열은  "3","23","423","2341"이 된다.

{3,2,4}까지는 얻을 수 있다.(3,23에서 3찾고 3제거-> 423에서 23 찾고 23제거, 4획득)

 

그러나 마지막 문자열, 423->2341에서 문제가 발생한다.

2341에서 423이라는 문자열을 찾지 못한다.

 

그러면 423의 모든 조합을 확인하는 방법이 있을 거 같아서 생각을 해보았으나

(234,243,...)

이러한 방법은 입력으로 주어진 문자열의 최대 길이가 1,000,000이기 떄문에 시간 상 불가능하다.

 

결국 문자열로서, 해결을 못했고, 아예 다른 방법이 필요했다.

---

처음에 문자열을 입력받을떄, 쉼표를 기준으로 정수를 만들어서 벡터에 넣는다.

그 후, 벡터를 순회하면서 중복이 없는 숫자만 뽑아내면 된다

 

#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;



bool cmp(string a,string b){
    if(a.size() != b.size()){
        return a.size() < b.size();
    }
    else{
        return a < b;
    }
}

vector<int> solution(string s) {
    //중복된 원소 존재
    //정해진 순서 다르면 다른 튜플

    map<int,bool> isExist;
    map<int,bool>::iterator iter;
    
    vector<int> answer;
    vector<string> tuples;
    string tempStr = "";
    bool isEnd = false;
    for(int i = 1;i<s.size()-1;i++){
        if(s[i] == '{'){
            tempStr = "";
            isEnd = false;
        }
        else if(s[i] == '}'){
            tuples.push_back(tempStr);
        }
        else{
            tempStr += s[i];
        }
        
    }
    
    
    sort(tuples.begin(),tuples.end(),cmp);
    string newStr = "";
    vector<int> allNumber;
    for(int i = 0;i<tuples.size();i++){
        newStr = "";
        for(int j = 0;j<tuples[i].size();j++){
            if(tuples[i][j] == ','){
                allNumber.push_back(stoi(newStr));
                newStr = "";
            }
            else{
                newStr += tuples[i][j];
            }
        }
        
        allNumber.push_back(stoi(newStr));
    }
    
    
    for(int i = 0;i<allNumber.size();i++){
       
        iter = isExist.find(allNumber[i]);
        if(iter == isExist.end()){
            answer.push_back(allNumber[i]);
            isExist.insert({allNumber[i],true});
        }
    }
    
    return answer;
}