프로그래밍

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

[난이도] Gold5
[유형] Stack

[풀이]
i:0~N-1 탑을 순회하면서 스택을 이용해 문제를 해결한다
1) stack이 비어있으면 왼쪽에 레이저를 가리는 탑이 없는 것으로 ans[i]=-1로 기록한다. (-1로 기록하는 이유는 마지막에 +1씩 해줄 것이기 때문에)

2) stack에 값이 있으면 i번 탑보다 큰 탑이 나오거나 stack이 빌 때까지 stack의 index들을 pop 해준다.
(이 탑들은 어차피 더 오른쪽에 있는 탑들에게는 i번 탑에 가려서 안보이므로 필요가 없다.)
case1) pop을 하다 stack이 빈 경우 : -1을 기록
case2) pop을 하다 큰 탑을 만난 경우 : 그 탑의 index를 push.

3) stack에 현재 index i를 push한다.

위의 과정을 반복하면 모든 index에 대해 답을 구할 수 있다.

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

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

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

[난이도] Gold4
[유형] Stack

[풀이]
새로운 string ans를 만들고 앞에서부터 하나씩 넣어보면서 PPAP가 채워지면 P로 바꾸는 식으로 문제를 해결한다.
1. 'A' 다음에 'P'가 오면 'A' 앞에는 무조건 'PP'가 있으므로 'PA'를 pop해주면 'P'만 남게되어 'PPAP'를 'P'로 바꾼게 된다.
2. 현재 'A'를 넣을 차례인데 앞에 두 문자가 'PP'가 아니면 'PPAP' 문자가 아니므로 ok flag를 0으로 설정한다.
3. 최종 ans 문자가 'PPAP'이거나 'P'이면 'PPAP' 문자이다.

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

#include <iostream>
#include <string>
using namespace std;
string s;
int main(){
    cin >> s;
    bool ok = 1;
    string ans;
    for(int i=0;i<s.size();i++){
        if(s[i]=='P'){
            if(ans.empty()) ans.push_back('P');
            else if(ans.back()=='A') ans.pop_back(),ans.pop_back();
            else ans.push_back('P');
        }else{
            if(ans.size()>=2 && ans.back()=='P'&&ans[ans.size()-2]=='P') ans.push_back('A');
            else {
                ok=0;
                break;
            }
        }
    }
    if(ans=="PPAP") ans="P";
    if(!ok || ans != "P") puts("NP");
    else puts("PPAP");
}

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

[풀이] 재귀,구현,Stack

문제에 써있는 대로 구현하면 된다.

1. 균형잡힌 괄호 문자열 찾기 int getBalance(string& s)

  여는 괄호와 닫는 괄호의 갯수가 같아지는 순간의 index를 반환

2. 올바른 문자열 체크 bool isRight(string& s)

  stack을 이용하였다. 여는 괄호의 경우 무조건 push, 닫는 괄호인 경우에

  stack이 비어있으면 올바른 괄호 문자열이 아니므로 false 리턴

위의 두 함수를 이용해서 재귀적으로 solution 함수를 채워주면 된다.

#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
string p = "()";
int getBalance(string& s) {
	int ret = 0;
	int l=0, r=0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '(') l++;
		else r++;
		if (l == r) {
			ret = i+1;
			break;
		}
	}
	return ret;
}

bool isRight(string& s) {
	stack<int> st;

	for (int i = 0; i < s.size(); i++) {
		char c = s[i];
		if (c == '(') {
			st.push(c);
		}
		else {
			if (st.empty()) {
				return false;
			}
			else {
				st.pop();
			}
		}

	}
	return true;
}
string rev(string& s) {
	string ret = "";
	for (int i = 1;i<s.size()-1;i++) {
		ret.push_back(s[i] == ')' ? '(' : ')');
	}
	return ret;
}

string solution(string p) {
	
	if (p == "") return p;
	string ret;

	int sz = getBalance(p);
	string w = p.substr(0, sz);
	string u = p.substr(sz, p.size() - sz);

	string k = solution(u);
	if (isRight(w)) {
		ret = w + k;
	}
	else {
		ret = "("+k+")";
		ret += rev(w);
	}
	return ret;
}

https://github.com/has2/Algorithm/blob/master/programmers/level2/%EA%B4%84%ED%98%B8%20%EB%B3%80%ED%99%98.cpp