[2019 kakao winter internship] 02. 튜플 (cpp/python)

튜플

프로그래머스

문제 설명

주어지는 s 원소들의 정보를 스플릿 하여 어떤 순서를 따르는 튜플을 찾아내는 문제이다.

즉, 주어지는 s에 있는 튜플들은 최종 순서와는 상관없이 주어지는데 이 튜플들의 원소 수가 작은 튜플부터 나열하여 최종 튜플의 순서를 찾아내면된다.

문제 풀이

소스코드 : C++

1. 우선 주어지는 s의 맨 처음과 끝은 각각 {, }이므로 1 ~ s.size() - 1까지 탐색한다.
2. {이면 하나의 튜플이 시작하는 시점이므로 튜플이 시작하는 지점을 의미하는 chk를 true로 바꿔주고 스플릿 하여 담아줄 이차원 벡터 str에 1차원 벡터 하나를 push하여 튜플을 담을 준비를 한다.
3. chk = true 인 상황(튜플의 시작)에서 , , } 모두 아닌 튜플의 원소인 경우에 string tmp에 하나씩 더해준다.
4. , 인 경우에는 하나의 원소가 다 담겨졌으므로 tmp에 들어있는 값을 int형 으로 변환 stoi(tmp)하여 str[idx]에 푸시 해주고 tmp를 비워준다.
5. }인 경우는 해당 튜플이 끝났으므로 tmp를 푸시하면서 idx를 하나 증가시켜주고 (다음 튜플을 탐색하겠다는 의미) chk=false 하여 튜플이 끝났음을 알려준다.
6. 위 과정을 반복하여 스플릿을 완료시킨 값들은 모두 str에 저장되어있다.
7. str을 미리 정의해둔 comp를 이용하여 튜플의 길이가 작은 순서대로 정렬한다.
8. 정렬한 str로 해당 원소를 key 값으로 하고 순서를 의미하는 idx를 value로 가지는 map과 vector<PII> ans에 넣어준다. ( map 을 이용하는 이유는 중복을 피하기 위함 )
9. ans를 idx순으로 정렬 하여 answer에 넣어준다.

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#define PII pair<int,int>

using namespace std;
bool comp(vector<int> a, vector<int> b) { return a.size() < b.size(); }
vector<int> solution(string s) {
    vector<int> answer;
    vector<vector<int>> str;
    unordered_map<int,int> um;    //idx, num
    bool chk = false;
    string tmp = "";
    int idx = 0;
    for (int i = 1; i < s.size() - 1; i++) {
        char c = s[i];
        if (c == '{') {
            chk = true;
            str.push_back(vector<int>());
        }
        else if (chk) {
            if (c == '}') {
                str[idx++].push_back(stoi(tmp));
                tmp.clear();
                chk = false;
            }
            else if(c==','){
                str[idx].push_back(stoi(tmp));
                tmp.clear();
            }
            else if (c != ',')tmp += c;
        }
    }    
    sort(str.begin(), str.end(), comp);
    idx = 1;
    vector<PII> ans;
    for (int i = 0; i < str.size(); i++) {
        for (int j = 0; j < str[i].size(); j++) {
            if (um.find(str[i][j])==um.end()) {
                um.insert({ str[i][j],idx });
                ans.push_back({ idx++,str[i][j] });
            }
        }
    }

    sort(ans.begin(), ans.end());
    for (auto res : ans)
        answer.push_back(res.second);

    return answer;
}
int main() {
    //string s = "{ {2},{2,1},{2,1,3},{2,1,3,4} }";
    //string s = "{{4,2,3},{3},{2,3,4,1},{2,3}}";
    //string s = "{{123}}";
    string s = "{{20,111},{111}}";
    for (auto ans : solution(s))
        cout << ans << " ";
    return 0;
}

소스코드 : Python

파이썬이 확실히 편하긴 편하다... 코드 길이 온도차이... ㅠㅜ

1. 리스트 슬라이싱을 이용하여 이번에는 맨 앞 두개 {{ 와 맨 뒤 두개 }}를 자른다.
   {{2},{2,1},{2,1,3},{2,1,3,4}} => 2},{2,1},{2,1,3},{2,1,3,4
2. 파이썬의 list.split은 스플릿의 기준만 있으면 알아서 잘라서 넣어준다.
   기준 : },{ 결과 : ['2', '2,1', '2,1,3', '2,1,3,4']
3. 리스트 s를 길이순으로 정렬해준다.
4. s의 원소들을 ,를 기준으로 스플릿 해준다.
5. answer에 tmp에 있는 원소가 없다면 answer.append해준다.
   중복제거

def solution(s):
    answer = []
    s = s[2:-2]
    s = s.split("},{")
    s.sort(key = len)
    for i in s:
        tmp = i.split(',')
        for j in tmp:
            if int(j) not in answer:
                answer.append(int(j))
    return answer

input_s = "{{2},{2,1},{2,1,3},{2,1,3,4}}" 
#input_s = "{{4,2,3},{3},{2,3,4,1},{2,3}}"
#input_s = "{{123}}"
#input_s = "{{20,111},{111}}"
print(solution(input_s))

그렇다면 cpp 을 python 과 비슷한 풀이 방식으로 풀 수는 없을까? python 에서 지원해주는 split 을 직접 구현해서 똑같은 풀이과정으로 풀어보았다.

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#define PII pair<int,int>

using namespace std;

bool comp(string a, string b){return a.size()<b.size();}
vector<string> split(string s, string delimiter){
    vector<string> ret;
    int pos_start = 0, pos_end = 0, delim_len = delimiter.size();
    string token;

    while((pos_end = s.find(delimiter, pos_start)) != string::npos){
        token = s.substr(pos_start, pos_end - pos_start);
        pos_start = pos_end + delim_len;
        ret.push_back(token);
    }
    ret.push_back(s.substr(pos_start));
    return ret;
}

vector<int> solution(string s) {
    vector<int> answer;
    s = s.substr(2,s.size()-4);
    vector<string> ret = split(s,"},{");
    sort(ret.begin(),ret.end(),comp);

    vector<string> tmp;
    for(auto i : ret){
        tmp = split(i,",");
        for(auto j : tmp){
            if(find(answer.begin(),answer.end(),stoi(j))==answer.end()){
                answer.push_back(stoi(j));
            }
        }
    }
    return answer;
}
int main() {
    //string s = "{ {2},{2,1},{2,1,3},{2,1,3,4} }";
    string s = "{{4,2,3},{3},{2,3,4,1},{2,3}}";
    //string s = "{{123}}";
    //string s = "{{20,111},{111}}";
    for (auto ans : solution(s))
        cout << ans << " ";
    return 0;
}

cpp 1번 코드 vs 2번 코드

1번 코드

2번 코드

속도 측면에서 많은 차이를 보인다 오히려 내 방식대로 푼 문제가 더 빠르다. unordered_map때문인가.. 코드 자체는 2번코드가 좀 더 깔끔하다.

split 구현한 부분에 대해서는 STL 포스팅에서 함께 하도록하겠다. Stack overflow 를 참조하면서 이해는 했지만 설명하기엔 좀 부족하다.

자료형의 형식이 자유로운 python 과는 달리 cpp 은 일일이 자료형을 맞춰주어야 하며 split을 구현하기위해서는 <string> 콘테이너에 대해서 좀 더 공부할 필요가 있어보인다.

알면 알수록 <algorithm>에는 유용한 함수들이 많다. 현재 나의 cpp풀이 방법은 그냥 내 생각대로 그대로 구현한 것이기 때문에 빈틈이 많다. 문제를 풀다보면 런타임 에러나 몇 개의 테스트 케이스를 틀린다던지...

예전에 c언어 스타일로 문제 풀때와는 달리 STL 을 많이 알게 됐다 싶었는데 어째 양파 같다.. 어디까지 알아둬야 좋은지... 나에게 유익한지 잘 모르겠다. 누군가 알려줄사람.. 멘토가 있었으면 좋겠다.

참조 :

Stack overflow

C++ reference