TIL (2021.01.06)

(1) 스택
3986 좋은 단어
평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자.

case 1:
3
ABAB
AABB
ABBA

-> 여기서는 AABB, ABBA가 좋은 단어

case 2:
3
AAA
AA
AB
-> AA가 좋은 단어

case 3:
1
ABBABB
-> ABBABB가 좋은 단어

애니팡을 생각해보면 좋을 것 같다. 같은 걸 한줄로 모았을 때 터지는 것 처럼, 얘네도 2개가 만났을 때 터진다. 하나도 남지 않으면 그게 좋은 단어!

stack을 이용하여, 전에 들어간 element가 지금 들어갈 element와 같으면 pop(), 아니면 push();

그래서 stack이 완전히 비게 되면 모두 짝을 만나 터졌다는 거니까, 좋은 단어 +=1, 그렇지 않으면 그냥 pass

 #include <iostream>
#include <stack>
using namespace std;

int main(){
    
    int number;
    cin>>number;
    
    int count = 0;
    
    string str;
    for(int i=0;i<number;i++){
        stack<char> st;
        cin>>str;
        for(int j=0;j<str.length();j++){
            if(st.empty()){
                st.push(str[j]);
            }else{
                if(st.top()==str[j]){
                    st.pop();
                }else{
                    st.push(str[j]);
                }
            }
        }
        
        if(st.empty()){
            count++;
        }
    }
    cout<<count;
}

(2) 큐
1966 프린터 큐

현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

우선순위 큐로 구현해보자!
#include < queue >
priority_queue<자료형> 이름 -> 내림차순에 따라 정렬
priority_queue<자료형, vector<자료형>, greater<자료형>> 이름

#include <iostream>
#include <queue>
using namespace std;

int main()
{
// n = 문서의 개수 m = Que에서 몇번째에 놓여있는가
    int testCase,n,m,importance,count;
    cin>>testCase;

    
    for(int i=0;i<testCase;i++){
        cin>>n>>m;
        count = 0;
        queue<pair<int,int>>que;
        priority_queue<int> pq;
        
        for(int j=0;j<n;j++){
            cin>>importance;
            que.push({j,importance});
            pq.push(importance);
        }
        
        while (!que.empty()) {
            int index = que.front().first;
            int value = que.front().second;
            que.pop();
            
            if(pq.top()== value){
                pq.pop();
                count+=1;
                
                if(index==m){
                    cout<<count<<endl;
                    break;
                }
            }else{
                que.push({index,value});
            }
        }
    }
}