[programmers] 프로그래머스 튜플(C++, Python)

(주)그렙

[programmers] 프로그래머스 튜플

(C++, Python)

(글쓴날 : 2020.05.09)

 

---

* programmers, 프로그래머스 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 튜플

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/64065

프로그래머스

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

특정 튜플을 표현하는 집합이 담긴 문자열이 주어질 때, 문자열이 표현하는 튜플을 구하는 문제입니다.

 

저의 경우, C++와 Python을 사용했습니다.

문자열을 차례대로 탐색하여 만약, 숫자일 시 큐에 저장하고, ,(쉼표) 혹은 }(닫는 중괄호)일 시 저장되어 있던 모든 숫자를 큐에서 빼어 나온 순서대로 합친 뒤, 문자열에서 표현하던 숫자로 변환하였습니다.

그 후, 문제의 조건에서 가능한 범위의 숫자와 해당 숫자의 개수를 저장하는 배열을 만들어 위에서 변환한 숫자들을 대입한 뒤, 숫자의 개수를 기준으로 내림차순 정렬하였고, 숫자의 개수가 0인 원소를 제외한 정렬된 순서대로 answer 배열에 저장하여 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
vector<int> solution(string s)
{
    struct cmp
    {
        bool operator()(pair<int, int> oldValue, pair<int, int> newValue)
        {
            return oldValue.second > newValue.second;
        }
    };
    vector<int> answer;
    vector<int> temp;
    int sLength = s.size();
    queue<char> q;
    string tempNum = "";
    bool isPop = false;
    string value = "";
    vector<pair<int, int>> hash;
 
    for (int i = 0; i < sLength; i++)
    {
        tempNum = "";
 
        if (s[i] != '{' && s[i] != '}')
            q.push(s[i]);
 
        if (s[i] == '}')
        {
            isPop = false;
 
            while (q.size())
            {
                isPop = true;
                value = q.front();
                q.pop();
 
                if (value != ",")
                    tempNum += value;
                else
                {
                    if (tempNum != "")
                    {
                        temp.push_back(stoi(tempNum));
                        tempNum = "";
                    }
                }
            }
 
            if (isPop && tempNum != "")
                temp.push_back(stoi(tempNum));
        }
    }
 
    for (int i = 0; i < 100001; i++)
        hash.push_back({i, 0});
 
    for (int i = 0; i < temp.size(); i++)
        hash[temp[i]].second++;
 
    sort(hash.begin(), hash.end(), cmp());
 
    for (int i = 0; i < 100001; i++)
    {
        if (!hash[i].second)
            break;
        answer.push_back(hash[i].first);
    }
 
    return answer;
}

---

* Python 코드

from collections import deque
 
 
def solution(s):
    answer = []
    sLength = len(s)
    dq = deque()
    
    for i in range(sLength):
        tempNum = ""
 
        if s[i] != "{" and s[i] != "}":
            dq.append(s[i])
 
        if s[i] == "}":
            isPop = False
 
            while(len(dq)):
                isPop = True
                value = dq.popleft()
                
                if value != ",":
                    tempNum += value
                else:
                    if tempNum != "":
                        answer.append(tempNum)
                        tempNum = ""
 
            if isPop and tempNum != "":
                answer.append(tempNum)
 
    hash = []
    for i in range(100001):
        hash.append([i, 0])
    
    for num in list(map(int, answer)):
        hash[num][1] += 1
        
    temp = sorted(hash, reverse=True, key=lambda x : x[1])
    
    answer = []
    for num in temp:
        if num[1] == 0:
            break
        answer.append(num[0])
        
    return answer

---