Programmers - 게임 맵 최단거리, 괄호 변환, 메뉴 리뉴얼

[ 게임 맵 최단거리 ] : < LV2 / 2374명 >

#include <vector>
#include <queue>

using namespace std;

struct V2
{
    int x, y;
    V2(int _x, int _y)
    {
        x = _x;
        y = _y;
    }
};

int solution(vector<vector<int>> maps)
{
    int answer = 0;
    //
    const int height = maps.size();
    const int width = maps[0].size();
    //
    vector<vector<bool>> open(height, vector<bool>(width, true));
    vector<vector<int>> dist(height, vector<int>(width, -1));
    // left, right, up, down
    vector<V2> dir { V2(-1, 0) , V2(+1, 0) , V2(0, -1) , V2(0, +1) };
    // begin
    queue<V2> q;
    q.push(V2(0, 0));
    open[0][0] = false;
    dist[0][0] = 1;
    while(q.empty() == false)
    {
        V2 cur = q.front();
        q.pop();
        //
        for(int j = 0; j < dir.size(); ++j)
        {
            V2 pos = V2(cur.x + dir[j].x, cur.y + dir[j].y);
            int x = pos.x, y = pos.y;
            bool inRange =  ((0 <= x && x < width) && (0 <= y && y < height));

            if(inRange && maps[y][x] && open[y][x])
            {
                q.push(V2(x, y));
                open[y][x] = false;
                dist[y][x] = dist[cur.y][cur.x] + 1;
            }
        }
    }
    //
    return dist[height-1][width-1];
}

# bfs(breadth-first search) : queue, struct

# 참고 : https://ansohxxn.github.io/programmers/114/

---

[ 괄호 변환 ] : < LV2 / 8396명 >

#include <string>
#include <vector>
#include <map>

using namespace std;

string Reversed(string s)
{
    string tmp = s.substr(1, s.size() - 2);
    //
    map<char, char> m;
    m['('] = ')';
    m[')'] = '(';
    //
    for(int i = 0; i < tmp.size(); ++i)
        tmp[i] = m[tmp[i]];
    //
    return tmp;
}

bool IsCorrect(string s)
{
    int pos = 0;
    while(true)
    {
        int pos = s.find("()");
        if(pos != string::npos)
            s.erase(pos, 2);
        else
            break;
    }
    //
    return s.empty();
}

bool IsBalanced(string s)
{
    map<char, int> m;
    //
    for(int i = 0; i < s.size(); ++i)
        ++m[s[i]];
    //
    return (m['('] == m[')']);
}

string Program(string p)
{
    if(p == "" || IsCorrect(p))
        return p;
    //
    string u = "", v = "";
    //
    int len = p.size();
    for(int i = 0; i < len; ++i)
    {
        u += p[i];
        if(IsBalanced(u))
        {
            v = p.substr(i+1, len-i-1);
            if(IsCorrect(u))
            {
                u += Program(v);
                return u;
            }
            else
            {
                string tmp = "";
                tmp += "(";
                tmp += Program(v);
                tmp += ")";
                tmp += Reversed(u);
                return tmp;
            }
        }
    }
    //
    return "";
}

string solution(string p)
{
    string answer = "";
    //
    answer = Program(p);
    //
    return answer;
}

# stl string class

  - void erase(pos, count)

  - string substr(pos, count)

---

[ 메뉴 리뉴얼 ] : < LV2 / 3602명 >

#include <string>
#include <vector>
//
#include <algorithm>
#include <map>
//
using namespace std;
// ========================================================== //
typedef pair<string, int> si;
// ========================================================== //
bool cmp(const si& a, const si& b)
{ // 내림차순
    return a.second > b.second;
}
// ========================================================== //
void findOrderPattern(map<string, int>& m, int courseSize, string order)
{
    sort(order.begin(), order.end());
    //
    int len = order.length();
    vector<bool> comb(len, false);
    //
    for(int i = 0; i < courseSize; ++i)
        comb[i] = true;
    //
    do
    {
        string pattern = "";
        for(int i = 0; i < len; ++i)
            if(comb[i])
                pattern += order[i];
        //
        m[pattern]++;
    } while(prev_permutation(comb.begin(), comb.end()));
}
// ========================================================== //
vector<string> solution(vector<string> orders, vector<int> course)
{
    vector<string> answer;
    //
    for(int menuCount : course)
    {
        map<string, int> m;
        // 주문패턴 저장
        for(string order : orders)
            findOrderPattern(m, menuCount, order);
        // 주문횟수 내림차순 정렬
        vector<si> v(m.begin(), m.end());
        sort(v.begin(), v.end(), cmp);
        // 2회 미만 주문 제외
        int maxCount = v.begin()->second;
        if(maxCount < 2)
            continue;
        else
        { // 최다주문 메뉴 추출
            auto iter = v.begin(), end = v.end();
            for(; iter != end; ++iter)
                if(iter->second == maxCount)
                    answer.push_back(iter->first);
        }
    }
    //
    sort(answer.begin(), answer.end());
    // 중복제거
    answer.erase(unique(answer.begin(), answer.end()), answer.end());
    //
    return answer;
}

# brute force 방식

# combination : comparator, prev_permutation

# STL vector : unique

# ETC : map, sort

---