Programmers - 튜플

---

title: Programmers - 튜플
date: 2022-07-16
tags:

• Algorithm

---

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

문제 요약

셀 수 있으며 중복 가능, 순서가 정해진 튜플이라는 것이 존재한다.
튜플의 원소가 n개일 때 n개의 부분 집합이 존재한다. 첫 번째 원소만 가지는 집합 하나, i번째 집합은 i-1번째 집합 + i번째 원소를 가지는 집합이다.
이러한 부분 집합 표현의 문자열로 튜플이 주어졌을 때, 해당 튜플을 vector에 순서에 맞춰 담아 return한다.

문제 풀이

설명은 길지만, 요약하면 위와 같이 짧고 단순하다.
간단히 숫자의 개수를 세야한다. 숫자의 개수에서 규칙을 찾을 수 있다.
첫 번째 원소는 모든 집합에 존재하므로 총 n개가 주어진다. 두 번째 원소는 n-1개, i번째 원소는 n - i + 1개만큼 존재한다.
그러므로 모든 수를 unordered_map에 count 하며, 개수에 따라 vector의 적절한 위치에 값을 넣어주면 된다.

총 문자열의 길이는 1M이지만, 부분 집합을 문자열로 표현했기에 괄호와 쉼표의 개수가 생각보다 많다.
심지어 튜플에 속한 원소의 개수는 최대 500개라고 명시했다. 최대 약 125K개의 수를 세면 되는 것이다.
효율성을 챙기고 싶다면 substring을 통해 수로 변환하는 과정, 그리고 unordered_map에 존재하는 원소들을 순회하는 과정에 중점을 두면 된다.

프로그램

#include <string>
#include <vector>
#include <unordered_map>

using std :: vector ;
using std :: string ;
using std :: unordered_map ;

vector < int > solution ( string s )
{
    int iStringSize = s.size () ;
    vector < int > answer ;
    unordered_map < int , int > umTupleCount ;
    const char * cpString = s.data () ;
    int iFirstNumberShowIndex = -1 ;



    for ( int i = 0 ; i < iStringSize ; ++i )
    {
        if ( ( -1 == iFirstNumberShowIndex ) && ( '0' <= cpString [ i ] ) && ( cpString [ i ] <= '9' ) )            // Find number start
        {
            iFirstNumberShowIndex = i ;
        }
        else if ( ( -1 != iFirstNumberShowIndex ) && ( ( cpString [ i ] < '0' ) || ( '9' < cpString [ i ] ) ) )        // Find number end
        {
            ++ umTupleCount [ stoi ( s.substr ( iFirstNumberShowIndex , i - iFirstNumberShowIndex ) ) ] ;
            iFirstNumberShowIndex = -1 ;
        }
    }

    int iTupleSize = umTupleCount.size () ;
    answer.resize ( iTupleSize , 0 ) ;

    for ( auto iter = umTupleCount.begin () ; iter != umTupleCount.end () ; ++ iter )                                // Update answer vector
    {
        answer [ iTupleSize - iter -> second ] = iter -> first ;
    }


    return answer ;
}