lv2 ) 괄호회전하기

https://school.programmers.co.kr/learn/courses/30/lessons/76502?language=cpp

 

#include<string>
#include<vector>
#include<queue>
#include<map>
#include<stack>

using namespace std;

bool IsValid(queue<char> q, const map<char, char>& bm)
{
    stack<char> st;
    int size = q.size();
    for(int idx = 0; idx < size; ++idx){
        char cur = q.front();
        q.pop();
        q.push(cur);
        
        if(!st.empty() && (bm.find(st.top()) != bm.end())) // st.top()이 bm이란 map에 등록된 키인지 확인
        {
            if(bm.at(st.top()) == cur)
            {
                st.pop();
                continue;
            }
        }
        else // bm.end이면 해당 키가 없다는 의미.
        {}
        st.push(cur);
    }
    return st.empty();
}

void moveS(queue<char>&q){
    char c = q.front();
    q.pop();
    q.push(c);
}
int solution(string s) {
    int answer = 0;
    queue<char> q;
    map<char, char> m = 
    {
        {'[',']'}, 
        {'{','}'},
        {'(',')'}
    };
    for(int idx = 0; idx < s.length(); ++idx){
        q.push(s[idx]);
    }
    for(int idx = 0; idx < s.length(); ++idx){
        answer += IsValid(q,m);
        moveS(q);
    }
    return answer;
}

풀이 설명 ( 못풀었다면 못푼이유 )

queue만으로 풀려했으나, find 함수를 지원하지 않기에 어떻게 해야 할지 잘 몰랐음.

 

해당 답지는 타인 코드 참조하며 해결했으며, queue는 rotate 목적

map에 조건을 등록.

 

stack은 qeueue에 map에 등록한 키의 값을 찾기 위한 용도이다.

 

stack에 값이 남아있으면 아다리가 안맞는다는 의미다.

 

이거 다시 풀어봐야 할듯하다. 이런 유형의 문제가 많이 나올 듯하고 결국 체화해야 할듯 하다.

 

unordered_map 만 해시맵으로 했을 때 사용했다.

 

사실 unordered_map(순서 상관x) 으로도 가능하다.

 

그러나 타인 코드를 참조해서 map(순서 중요)을 사용했다.

bm.find(st.top()) != bm.end())

이게 중요하다.

map에서 find 가 가능하고 해당 키가 없으면 end()가 된다는 것이고

키를 찾으면 ≠ bm.end() 까지 안 간다는 것이다.

 

 

 

다시 풀이(3.23)

#include <string>
#include <vector>
#include<unordered_map>
#include<iostream>
#include<queue>
#include<stack>

using namespace std;

void leftMove(queue<char>& q){
    char t = q.front();
    q.pop();
    q.push(t);
}

bool isSuccess(queue<char> q, const unordered_map<char, char> um)
{
    stack<char> st;
    int sizeQ = q.size();
    for(int idx = 0; idx < sizeQ; ++idx){
        char t = q.front();
        q.pop();
        q.push(t);
        if(!st.empty() && um.find(st.top()) != um.end()) // st.top() 대신 t를 놓으면 키가 아닌 문자
        {
            //unordered_map or map의 at(key) 는
            //키가 없으면 예외를 던진다.
            //-1 같은 값을 반환하지 않는다.
            // 위 find 조건에서 st.top이 아닌 t로 하면 st의 top이 (, {, [ 중
            // 하나가 아닌 그 반대값을 찾을 수 있다. 이럴 때 예외를 던지게 된다.
            // 그렇기에 st.top()이 ( { [ 중 하나인걸 find로 체크하고
            // t가 um에서의 st.top 키의 값인 지를 체크 해야한다.
            if(t == um.at(st.top())){ 
                st.pop();
                continue;
            }
        }
        
        st.push(t);
    }
    
    return st.empty();
}
int solution(string s) {
    int answer = 0;
    queue<char>q;
    for(int idx = 0; idx < s.length();++idx)
    {
        q.push(s[idx]);
    }

    unordered_map<char, char> um = 
    {
        {'{','}'},
        {'[',']'},
        {'(',')'}
    };
    for(int idx = 0; idx < s.length();++idx)
    {
        if(isSuccess(q, um)){
            answer++;
        }
        leftMove(q);
    }
    return answer;
}