프로그래밍

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

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

[풀이]
실버1치고 발상이 어려워서 다른 분들의 풀이를 참고했습니다.
(()[[]]) = 2 * (2+3*3) = 2*2 + 2*3*3 이 되는 분배법칙을 이용합니다.
cur 변수를 1로 초기화 해놓고
- 여는 괄호 ( 가 나오면 2를 [가 나오면 3을 곱해줍니다.
- 닫는 괄호가 나오면 해당 괄호가 cur에 미치는 영향은 끝났으므로 2 또는 3으로 나눠줍니다.
  예를 들어, (()[[]]) = 2 * (2+3*3) 에서 두번 째 첫 번째 ) 가 나왔을 때, cur은 2*2에서 2*2/2 가 되어 다시 2가 됩니다.
  그래야, 3*3에 2만 곱해줄 수 있기 때문입니다.
- () 혹은 [] 모양의 인접한 올바른 문자열이라면 2*2 + 2*3*3 에서 한 덩어리의 값이 끝남을 의미하므로 나누기 전에 cur의 값을 total에 더해 줍니다.
- 중간중간 올바른 문자열이 아닌 경우를 체크하여 0을 return 해줍니다.
- 모든 문자열을 순회하고도 stack에 값이 남아있다면 올바른 문자열이 아니므로 0을 return 해줍니다.

#include <cstdio>
#include <stack>
#include <string>
#include <iostream>
using namespace std;
string s;
int sol(){
    stack<char> st;
    int total=0,cur=1;
    for(int i=0;i<s.size();i++){
        if(s[i]=='('){
            cur*=2;
            st.push(s[i]);
        }else if(s[i]=='['){
            cur*=3;
            st.push(s[i]);
        }else{
            if(st.empty()) return 0;
            if(s[i]==')') {
                if(st.top()!='(') return 0;
            }else{
                if(st.top()!='[') return 0;
            }
            st.pop();
            if(s[i-1]=='('||s[i-1]=='[') total+=cur;
            if(s[i]==')') {
                cur/=2;
            }else{
                cur/=3;
            }
        }
    }
    if(!st.empty()) return 0;
    return total;
}
int main(){
    cin >> s;
    cout << sol();
}

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

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

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

[풀이]
stack을 이용해 모든 괄호쌍의 위치를 저장한 뒤,
괄호쌍을 고르는 모든 경우의 수를 브루트포스를 이용해 구해준 뒤,
선택된 괄호쌍의 괄호들을 제거한 string을 set에 저장한 뒤 순회하며 출력해주면 됩니다.
괄호쌍의 최대 개수가 10개로 제한되어 있으므로 브루트포스를 이용할 수 있습니다.

#include <iostream>
#include <string>
#include <stack>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
string s;
vector<pair<int,int>> v;
int main(){
    cin >> s;
    stack<int> st;
    for(int i=0;i<s.size();i++){
        char c = s[i];
        if(c=='(') st.push(i);
        else if(c==')'){
            v.push_back({st.top(),i});
            st.pop();
        }
    }
    set<string> ans;
    int n = v.size();
    for(int i=1;i<(1<<n);i++){
        vector<bool> erased(s.size());
        for(int j=0;j<n;j++){
            if(((1<<j)&i)>0) erased[v[j].first]=erased[v[j].second]=1;
        }
        string tmp;
        for(int j=0;j<s.size();j++){
            if(!erased[j]) tmp+=s[j];
        }
        ans.insert(tmp);
    }
    for(auto a : ans) cout << a << '\n';
}

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

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

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

[풀이]
이 문제와 같이 여는괄호 닫는괄호가 나오면 보통 stack을 활용하여 푸는 문제입니다.
stack<char> 형태의 char형을 저장하는 스택을 선언하여 실제로 압축을 해제하며 저장하면
메모리 초과가 발생하게 됩니다.
stack<int>형 스택을 선언하여 문자열의 실제 길이를 int 값으로 저장해주어야 합니다.

풀이는 다음과 같습니다.

문자열을 앞에서부터 순회하면서
  i) '(' 인 경우
    '('를 숫자와 구분하기 위해 절대 나올 수 없는 수인 -1을 push 해줍니다.

 ii) 숫자인 경우
    뒤의 문자가 '('인 경우 문자의 길이를 곱할 때 사용해야 하므로 숫자 그대로 스택에 push 해줍니다.
    그 외의 경우에는 어떤 숫자이든 결국 문자열의 길이로는 1의 가치가 있기 때문에 1을 push 해줍니다.

iii) ')' 인 경우
    스택의 top이 '(' (즉, -1) 일 때까지 pop하며 len에 더해준 뒤,
    '(' 를 pop 한 뒤의 top과 곱해준 뒤 한번 더 pop을 해줍니다.
    예를 들어, 3(1111) 인 경우 (1+1+1+1)*3을 해주라는 의미입니다.
    이 숫자를 다시 stack에 push하여 다음 연산에 사용합니다.

위 과정을 완료 한 뒤 stack의 모든 정수를 더해주면 최종 정답이 됩니다.

#include <string>
#include <iostream>
#include <stack>
#include <vector>
#include <cctype>
using namespace std;
string s;
int main(){
    cin >> s;
    stack<int> st;
    for(int i=0;i<s.size();i++){
        if(s[i]=='(') st.push(-1);
        else if(isalnum(s[i])){
            if(i<s.size()-1 && s[i+1]=='(') st.push(s[i]-'0');
            else st.push(1);
        }else{
            int len=0;
            while(st.top()!=-1) {
                len+=st.top();
                st.pop();
            }
            st.pop();
            len*=st.top(); st.pop();
            st.push(len);
        }
    }
    int ans=0;
    while(!st.empty()){
        ans+=st.top();
        st.pop();
    }
    printf("%d",ans);
}

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

https://programmers.co.kr/learn/courses/30/lessons/76502

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

[풀이]
전형적인 스택 문제입니다.

#include <string>
#include <vector>
#include <list>
#include <stack>
using namespace std;
list<char> li;

bool check(){
    stack<char> st;
    for(auto c : li){
        if(c=='['||c=='{'||c=='(') st.push(c);
        else {
            if(st.empty()) return 0;
            if(c==']'){
                if(st.top()!='[') return 0;
            }
            if(c=='}'){
                if(st.top()!='{') return 0;
            }            
            if(c==')'){
                if(st.top()!='(') return 0;
            }        
            st.pop();
        }
    }
    return st.empty();
}

int solution(string s) {
    int ans=0; 
    for(char c : s) li.push_back(c);

    for(int i=0;i<s.size();i++){
        ans+=check();

        li.push_back(li.front());
        li.pop_front();
    }

    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/괄호 회전하기.cpp

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

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

[풀이]
stack을 이용해 0이면 pop, 아니면 push를 해주고 스택에 남은 모든 원소를 더하면 된다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var k = readLine().toInt()
    var st = Stack<Int>()
    while(k-->0){
        var ip = readLine().toInt()
        when(ip){
            0 -> st.pop()
            else -> st.push(ip)
        }
    }
    var ans = 0
    while(!st.empty()) ans += st.pop()
    println(ans)
}

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

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

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

[풀이]
N이 8만으로 N^2 풀이는 불가능하므로 스택을 이용해서 풀어야 한다.

0번 건물의 index부터 차례로 stack에 집어넣으면서 stack에 들어있는 건물의 높이가 내림차순이 되도록 유지한다.
내림차순이 되게 하려면 스택의 top인 건물이 현재 확인중인 i번 건물보다 낮아질때까지 pop을 해줘야 한다.
pop 되어야할 i보다 낮은 k번 건물은 i-k-1 만큼의 건물을 볼수 있다. (k~i-1 까지 내림차순인 것이 보장되므로)
그러므로 pop할때마다 ans에 i-k-1만큼을 더해주면 ans가 답이다.

N이 80000이고 건물이 모두 내림차순으로 되어있다면 정답이 int 범위를 넘어가므로 long long을 사용해야 한다.

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

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

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

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

[풀이]
스택 문제이지만 스택을 사용하지 않아도 해결이 가능하다.

0~N-1 문자를 순회하면서
1) s[i]가 '(' 인 경우 s[i+1]이 ')' 이면 레이저이고 아니면 쇠막대기의 왼쪽끝이다.
쇠막대기인 경우, 현재 쌓여있는 막대 개수 cnt를 1 증가시켜준다
레이저인 경우, 현재 쌓인 막대기만큼 ans에 더해주고 index를 한칸 넘어간다 ( ')'를 스킵해야 하므로 )

2) s[i]가 ')' 인 경우
막대가 끝났으므로 cnt를 1 감소시키고
ans에 1을 더해준다. 왜나하면 막대의 맨 오른쪽 조각을 더해줘야 하므로

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var s = readLine()
    var cnt=0
    var ans=0
    var i=0
    while(i<s.length){
        when(s[i]){
            '('->{
                if(s[i+1]==')') {
                    ans+=cnt
                    i++
                }
                else cnt++
            }
            else->{
                ans++
                cnt--
            }
        }
        i++
    }
    println(ans)
}

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

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

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

[풀이]
Left Stack와 Right Stack 두가지 스택을 이용하여 문제를 해결하면 된다.
커서를 우측으로 옮길때는 Left stack의 top을 Right stack으로,
그 반대는 Right stack의 top를 Left stack으로,
커서에 문자를 추가하거나 제거할때는 Left stack에 추가,제거

LinkedList를 이용해도 삽입,제거 연산이 O(1)이므로 문제를 시간내에 풀 수 있다.
Kotlin에서 List가 아닌 LinkedList를 사용해야한다.

[스택 풀이]

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var s = readLine()
    val lst = Stack<Char>()
    var rst = Stack<Char>()
    for(a in s) lst.push(a)
    for(i in 1..readLine().toInt()) {
        var ip = readLine().split(' ')
        when (ip[0]) {
            "L" -> if(!lst.empty()) rst.push(lst.pop())
            "D" -> if(!rst.empty()) lst.push(rst.pop())
            "B" -> if(!lst.empty()) lst.pop()
            else -> {
                lst.push(ip[1][0])
            }
        }
    }
    println(lst.toCharArray()+rst.toCharArray().reversed())
}

[LinkedList 풀이]

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var s = readLine()
    var list = LinkedList<Char>()
    for(a in s) list.add(a)
    var it = list.listIterator()
    while(it.hasNext()) it.next()
    var n = readLine().toInt()
    for(i in 1..n) {
        var ip = readLine().split(' ')
        when (ip[0]) {
            "L" -> if (it.hasPrevious()) it.previous()
            "D" -> if (it.hasNext()) it.next()
            "B" -> {
                if (it.hasPrevious()) {
                    it.previous()
                    it.remove()
                }
            }
            else -> it.add(ip[1][0])
        }
    }
    println(list.toCharArray())
}

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