프로그래밍

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

[난이도] Silver3
[유형] 스택

[풀이]
1~n 순서로 무조건 push해야 하므로 for문을 돌면서 일단 push해주고
만약 top이 현재 나와야 하는 수열 값이라면 while문을 돌면서 pop을 해준다.
만약 위 과정을 마치고 스택이 비어있지 않다면 수열을 만들 수 없는 경우이다.

복잡하게 조건을 생각하면서 풀려고 하면 어렵기 때문에 스택의 empty 유무로 판단해야 한다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.collections.ArrayList

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var n = readLine().toInt()
    val st = Stack<Int>()
    val arr = IntArray(n)
    for(i in 0..n-1) arr[i]=readLine().toInt()
    var idx=0;
    var ans=ArrayList<Char>()
    for(i in 1..n){
        st.push(i)
        ans.add('+')
        while(!st.empty() && st.peek()==arr[idx]){
            st.pop()
            ans.add('-')
            idx++
        }
    }
    if(!st.empty()) println("NO")
    else for(c in ans) println(c)
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver3/1874.cpp

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

[난이도] Silver4
[유형] 스택

[풀이]
코틀린으로 문제를 풀때 입력은 BufferedReader(InputStreamReader(System.`in`)) 으로 받는 것이 좋다.
Scanner로 받으니까 시간초과가 났다

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    var n = readLine().toInt()
    var s = Stack<Int>()
    while(n-->0){
        var rd = readLine().split(" ")

        val ret = when(rd[0]){
            "push" -> {
                var v = rd[1].toInt()
                s.push(v)
                null
            }
            "pop" -> {
                if(!s.empty()) s.pop()
                else -1
            }
            "top" -> {
                if(!s.empty()) s.peek()
                else -1
            }
            "size" -> s.size
            else -> {
                if(s.empty()) 1
                else 0
            }
        }
        ret?.let{println(ret)}
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver4/10828.cpp

www.acmicpc.net/problem/9935

[난이도] Gold4

[유형] 스택

[풀이]

A를 전체 문자열 B를 폭발 문자열이라고 했을 때
A를 i: 0~N-1까지 순회하면서 i와 A[i]의 B에서의 index를 스택에 저장
방식으로 답을 구한다.

#include <stack>
#include <iostream>
#include <string>
using namespace std;
bool erase[1000001];
string a,b;
stack<pair<int,int>> s;
int main(){
    cin >> a >> b;
    if(b.size()==1){
        for(int i=0;i<a.size();i++) if(a[i]==b[0]) erase[i] = 1;
    }else{
        for(int i=0;i<a.size();i++){
            if(!s.empty() && b[s.top().second+1]==a[i]){
                s.push({i,s.top().second+1});
                if(s.top().second==b.size()-1) {
                    int sz = b.size();
                    while(sz--) {
                        erase[s.top().first] = 1;
                        s.pop();
                    }
                }
            }
            else if(a[i]==b[0]) s.push({i,0});   
            else while(!s.empty()) s.pop();
        }
    }
    string ret;
    for(int i=0;i<a.size();i++) if(!erase[i]) ret += a[i];
    if(ret=="") puts("FRULA"); 
    else cout << ret;
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/9935.cpp

www.acmicpc.net/problem/1918

[난이도] Gold4

[유형] 스택 (중위표기법 -> 후위표기법)

[풀이] 스택 (중위표기법 -> 후위표기법)

연산자 우선순위와 Stack을 이용. 연산자의 우선순위는 ( < -,+ < /,* : )는 Stack에 들어가지 않으므로 정의하지 않는다. 문자열을 순회하면서

1. 피연산자면 바로 출력

2. '('이면 스택에 push

3. ')'이면 여는 괄호가 나올때까지 스택의 원소를 팝하면서 출력

4. Stack이 비어있거나 Stack의 top보다 우선순위가 낮아질때까지 Stack의 top을 pop하면서 출력 후 push ('('인 경우 2에서 예외로 무조건 push)

4번에서 while문을 통해 반복해주는 것이 중요.

#include <stack>
#include <iostream>
#include <cctype>
#include <string>
using namespace std;
string a,ret;
int p(char c){
    if(c=='(') return 0;
    if(c=='+'||c=='-') return 1;
    return 2;
}
int main(){
    cin >> a;
    stack<char> s; 
    for(char c : a){
        if(isalpha(c)) ret+=c;
        else if(c=='(') s.push(c);
        else if(c==')'){
            while(1){
                char op = s.top(); s.pop();
                if(op=='(') break;
                ret+=op;
            }
        }
        else{
            while(!s.empty() && p(s.top()) >= p(c)) {
                ret+=s.top();
                s.pop();
            }
            s.push(c);
        }
    }
    while(!s.empty()) {
        ret+=s.top();
        s.pop();
    }
    cout << ret;
} 

github.com/has2/Problem-Solving/commit/f60ec108a19e4d6d59156a99880d7e222b1a3f26

www.acmicpc.net/problem/17298

[난이도] Gold4

[유형] Stack

[풀이]

1. 스택이 비어있으면 index push

2. 스택에 원소가 있을때 현재 값보다 작은 원소들은 NGE가 현재 값으로 정하고 pop

#include <cstdio>
#include <stack>
using namespace std;
int N,a[1000000],nge[1000000];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%d",&a[i]);
        nge[i]=-1;
    }
    stack<int> st;
    for(int i=0;i<N;i++){
        while(!st.empty() && a[i] > a[st.top()]) {
            nge[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    for(int i=0;i<N;i++) printf("%d ",nge[i]);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/17298.cpp