[C++] 6월 16일 코딩 테스트 수업

프로그래머스 봉인된 주문

진수법을 이용하여 문제을 해결

 

이거 지금 맵핑 이용해서 해결해볼려고 하다가 다 못함 ㅇㅇ 

#include <iostream>
#include <string>
#include <map>

void toKeys(int nNumbers, std::map<int, char> &map, std::string& str);

int main()
{
    std::map<int, char> map{};
    std::string str{};


    for (int i = 0; i < 26; i++)
    {
        map.insert({ i, i + 97 });
    }

    for (auto iter : map)
    {
        printf("%c", iter.first);
        printf("%d", iter.second);
        printf("\n");
    }

    //toKeys(24, map,str);
    //toKeys(25, map,str);
    //toKeys(26, map,str);
    //toKeys(27, map,str);
    //toKeys(28, map,str);
}

//void toKeys(int nNumbers, std::map<int, char>& map, std::string& str)
//{
//
//    for(auto iter : map)
//    { }
//    while (nNumbers > 0)
//    {
//        int nData = nNumbers % 27;
//        
//        
//        printf("%c", );
//        if (nNumbers = nNumbers % 27 == 0)
//            
//        else
//            nNumbers = nNumbers / 27;
//    }
//    printf("\n");
//}
/*
void toKeys(int nNumbers, std::string& str)
{
    int nArg = 26; // 진수 변환  
    int nPivot{};
    int nData = 1;

    while ((nNumbers / nData) > 0)
    {
        nData = nData * nArg;
        nPivot++;
    }
    nData /= nArg; // 이거 곱하면 넘어가니까 한번 나눠줌 
    printf("%d\n", nData);

    for (int i = 0; i < nPivot; i++)
    {
        printf("%c\n", (nNumbers / nData) + 97);
        nNumbers = nNumbers % nData;
        nData = nData / nArg;
    }
}

// 10진수로 만드는 코드
int toint(const char* str)
{
    int nNumber{};

    while (*str)
    {
        int nData{};

        if (*str >= '0' && *str <= '9')
            nData = *str - 48;
        else if (*str >= 'a' && *str <= 'z')
            nData = *str - 87;  // a : 10 , b : 11, c : 12 .... 이런식으로 접근할꺼임
        
        nNumber = 16 * nNumber + nData;
        str++;
    }
    return nNumber;
}


int toint(const char* str)
{
    int nNumber{};

    while (*str)
    {
        nNumber = 26 * nNumber + (*str - 96);
        str++;
    }
    return nNumber;
}
*/

 

map에 데이터를 넣고, BFS를 사용하여 문제해결

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <queue>
#include <unordered_set>


void toKeys(int n, std::map<int, std::string>& map, std::string& str, const std::vector<std::string>& bans);

int main()
{
    std::map<int, std::string> map{};
    std::string str{};
    std::vector<std::string> bans{ "d", "e", "bb", "aa", "ae" };

    for (int i = 0; i < 26; i++)
    {
        map.insert({ i, std::string(1, (char)(i + 97)) });
    }

    int n = 30;
    toKeys(n, map, str, bans);

    std::cout << n << "번째 주문은 " << str << " 입니다.\n";
}

void toKeys(int n, std::map<int, std::string>& map, std::string& str, const std::vector<std::string>& bans)
{
    std::unordered_set<std::string> banSet(bans.begin(), bans.end());
    std::queue<std::string> q;

    for (int i = 0; i < 26; i++)
    {
        q.push(map[i]);
    }

    while (!q.empty())
    {
        std::string cur = q.front();
        q.pop();

        if (banSet.find(cur) == banSet.end())
        {
            n--;
            if (n == 0)
            {
                str = cur;
                return;
            }
        }

        if (cur.length() < 11)
        {
            for (int i = 0; i < 26; i++)
            {
                q.push(cur + map[i]);
            }
        }
    }
    str.clear();
}