2022-05-17 알고리즘 문제

https://www.acmicpc.net/problem/5568

5568번: 카드 놓기

백트래킹과 map사용해서 푼 문제

#include <iostream>
#include <map>
#include <string>
using namespace std;
int n,k;
string arr[11];
bool visited[11];
map<int,int> m;
string A[11];
 
void dfs(int start){
    if(start == k){
        int number = 0;
        string temp = "";
        for(int i = 0;i<n;i++){
            temp = temp + arr[i];
        }
        number = stoi(temp);
        m.insert(pair<int,int>(number,number));
        return;
    }
    for(int i = 0;i<n;i++){
        if(visited[i] == false){
            visited[i] = true;
            arr[start] = A[i];
            dfs(start+1);
            visited[i] = false;
        }
    }
 
}
int main(void){
    cin >> n;
    cin >> k;
    for(int i = 0;i<n;i++){
        cin >> A[i];
    }
    dfs(0);
    cout << m.size();
}

---

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

---

중위표기법 → 후위표기법

1. 피연산자의 경우 스택에 넣지 않고 그냥 출력한다.
2. 연산자의 경우 2가지로 나뉜다.
   1. 스택이 비어있을 경우 PUSH
   2. 스택이 비어있지 않을 경우 스택의 top에 있는연산자와 우선순위를 비교해서 , stack의 top연산자가 현재 연산자의 우선순위보다 낮을 때까지 Pop후 출력
   3. 현재 연산자 Push
3. 왼쪽 괄호 ‘(’를 만나면 Push
4. 오른쪽 괄호 ‘)’를 만나면 왼쪽 괄호 ‘(’가 나올때까지 모든 연산자 Pop후 출력
   1. 이때 스택의 Top안 ( 도 Pop해주기

연산자 우선순위

1️⃣ ✖️(곱), ➗(나누기), ^ , % (나머지 연산)

2️⃣ ➕ , ➖

3️⃣ ( (왼쪽 괄호)

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int width(char c){
    if(c == '*' || c == '/'){ //*와 나누기-> 가장 큰 가중치
        return 3;
    }
    else if(c == '+' || c == '-'){ //+와 뺴기(-) -> 두번쨰로 큰 가중치
        return 2;
    }
    else if(c == '('){ //연산자 중 가장 낮은 가중치
        return 0;
    }
    else{ //연산자가 아닌 경우
        return -1;
    }
}
 
int main(void){
    stack<pair<char,int>> st; //연산자와 가중치를 담을 stack
    string str;
    cin >> str;
    
    for(int i = 0;i<str.size();i++){
        int w = width(str[i]);
        if(w == -1 && str[i] != ')'){
            cout << str[i];
        }
        else if(str[i] == ')' && w == -1){
            while(st.top().first != '('){
                if(st.empty()){
                    break;
                }
                if(st.top().first != '('){
                    cout << st.top().first;
                    st.pop();
                }
            }
            if(st.top().first == '('){
            	st.pop();
            }
        }
        else if(w != -1){
            if(w == 0){
                st.push({str[i],w});
            }
            else if(w == 2){
                if(st.empty()){
                    st.push({str[i],w});
                }
                else{
                    while(1){
                        if(st.empty()){
                            break;
                        }
                        else if(st.top().second < w){
                            break;
                        }
                        cout << st.top().first;
                        st.pop();
                    }
                    st.push({str[i],w});
                }
            }
            else if(w == 3){
                if(st.empty()){
                    st.push({str[i],w});
                }
                else{
                    while(1){
                        if(st.empty()){
                            break;
                        }
                        else if(st.top().second < w){
                            break;
                        }
                        cout << st.top().first;
                        st.pop();
                    }
                    st.push({str[i],w});
                }
            }
        }
    }
    while(!st.empty()){
        cout << st.top().first;
        st.pop();
    }
 
}