📝10828번: 스택
문제 설명
스택
해결 방법
1. C++ STL에서 제공하는 stack을 사용하는 방법push는 스택에 원소를 삽입하는 연산
size는 스택의 크기를 구하는 연산
top은 스택의 가장 마지막에 들어온 원소를 반환하는 연산
pop은 top에 있는 원소를 제거하고 반환하는 연산
empty는 스택이 비어있는지 확인하는 연산으로 비어있다면 1, 비어 있지 않다면 0을 반환한다.
주의할 점은 pop, top 연산 시 스택이 비어있다면 -1을 출력해야 한다.
- 직접 구현하는 방법
C++에서 제공하는 STL이 있기 때문에 직접 구현하지는 않았다. 실력 좋은 개발자들이 구현해놓은 걸 가져다 썼다. 하지만 구현도 할 줄 알아야 한다고 생각한다.
💻소스코드
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
stack<int> st;
string str;
for (int i = 0; i < N; i++) {
cin >> str;
if (str == "push") {
int num;
cin >> num;
st.push(num);
}
else if (str == "size") {
cout << st.size() << "\n";
}
else if (str == "top") {
if (!st.empty())
cout << st.top() << "\n";
else
cout << "-1\n";
}
else if (str == "pop") {
if (!st.empty()) {
cout << st.top() << "\n";
st.pop();
}
else
cout <<"-1\n";
}
else if (str == "empty") {
if (!st.empty())
cout << "0\n";
else
cout << "1\n";
}
}
return 0;
}📝10773번: 제로
문제 설명
제로
해결 방법
K번의 입력을 하면서 0이 아니면 스택에 push()하고 0이면 pop()한다.
스택이 비어있으면 0을 출력, 비어있지 않으면 스택 top의 원소를 더하고 pop()을 스택이 비워질 때까지 반복한다.
다 더한 값sum을 출력한다.
💻소스코드
#include <iostream>
#include <stack>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int K, num;
int sum = 0;
stack<int> st;
cin >> K;
for (int i = 0; i < K; i++) {
cin >> num;
if (num != 0)
st.push(num);
else
st.pop();
}
if (st.empty())
cout << "0\n";
else {
while (!st.empty()) {
sum += st.top();
st.pop();
}
cout << sum << "\n";
}
return 0;
}📝9012번: 괄호
문제 설명
괄호
해결 방법
괄호 쌍이 맞으면 Valid PS로 YES를 출력, 아니면 NO를 출력한다.
NO는 '('만 남거나, ')'만 남는 경우, ")("와 같은 형태로 남는 경우이다. "()"쌍만 인정한다.
괄호 문자열 PS를 입력받아서 문자 하나씩 검사를 한다.
is_invalid는 괄호 문자열이 PS인지 검사하는 목적으로 선언한다.
'('일 경우에만 stack에 push 한다.
')'일 경우 stack이 비어있지 않고 '('가 있다면 쌍이 맞다는 의미이므로 pop한다.
스택이 비어있지 않다는 조건을 빠뜨린다면 segmentation fault 에러가 발생한다.
비어있는 스택에 top() 연산 시 top은 배열 인덱스의 범위 밖인 -1을 가리키고 있기 때문이라고 생각한다.
')'가 남아있는데 스택이 비었다면 뒤에 '('가 있더라도 쌍이 맞지 않았다는 뜻이므로 is_invalid에 true를 할당하고 더 이상 검사할 필요가 없으므로 break 한다.
스택이 비어있지 않거나 is_invalid가 true라면 VPS가 아니므로 NO를 출력하고, 아닌 모든 경우에 대해 YES를 출력한다.
bool is_invalid = false;for문 바깥에서 초기화하면 모든 케이스에 대해서 항상 NO만 출력되었다. 하지만 for문 안에서 값을 할당해주면 제대로 출력되었다.명쾌한 이유를 찾지 못했다.
💻소스코드
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main()
{
// 괄호
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T; // 테스트 케이스
string PS; // 괄호 문자열
bool is_invalid; // 괄호 문자열 판별, false가 Valid PS
for (int i = 0; i < T; i++) {
stack<char> st;
cin >> PS;
is_invalid = false;
for (int j = 0; j < PS.size(); j++) {
if (PS[j] == '(')
st.push(PS[j]);
else if (PS[j] == ')' && !st.empty())
st.pop();
else if (PS[j] == ')' && st.empty()) {
is_invalid = true;
break;
}
}
// 스택이 비어있지 않으면 '('는 남는데, ')'가 없어서 쌍이 맞지 않다
// is_invalid가 true면 '('는 없는데, ')'가 남아서 쌍이 맞지 않다
if (!st.empty() || is_invalid == true)
cout << "NO\n";
else
cout << "YES\n";
}
return 0;
}📝4949번: 균형잡힌 세상
문제 설명
균형잡힌 세상
해결 방법
괄호[]쌍과()쌍이 반드시 맞아야 한다.[)(])(][등등 전부 no다.
입력으로.마침표가 들어왔을 때 while loop 종료 조건을 설정한다.
공백을 포함한 문자열을 입력으로 받아야 하므로 getline() 함수를 활용한다.
문자열 마지막에.마침표가 있으면 문자열 검사를 종료하고 yes or no를 출력한다.
문자열을 검사하면서(또는[일 경우에만 stack에 push 한다.
)또는]일 때, stack의 top이(또는[이면 괄호 쌍이 맞았기 때문에 pop 한다.
괄호만 확인하면 되기 때문에 공백이나 소문자, 대문자는 continue로 건너뛴다.
위의 조건들이 아닐 땐][)([)(]와 같은 조건이므로 is_invalid에 true를 주고 더 이상 확인할 필요 없으므로 break 한다.
스택이 비어있지 않거나, is_invalid가 true면 no를 출력, 아니면 yes를 출력한다.
💻소스코드
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
// 균형잡힌 세상
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
while (true) {
string str;
getline(cin, str);
stack<char> stk;
bool is_invalid = false;
if (str[0] == '.') // 종료조건
break;
for (int i = 0; i < str.size(); i++) {
if (str[i] == '.')
break;
if (str[i] == '(' || str[i] == '[')
stk.push(str[i]);
else if (str[i] == ')' && !stk.empty() && stk.top() == '(')
stk.pop();
else if (str[i] == ']' && !stk.empty() && stk.top() == '[')
stk.pop();
else if (str[i] == ' ' || ('a' <= str[i] && str[i] <= 'z') || ('A' <= str[i] && str[i] <= 'Z'))
continue;
else {
is_invalid = true;
break;
}
}
if (!stk.empty() || is_invalid == true)
cout << "no\n";
else
cout << "yes\n";
}
return 0;
}📝1874번: 스택 수열
문제 설명
스택 수열
해결 방법
1부터 n까지에 수에 대해 차례로 [push 1, push 2, push 3, push 4, pop -4, pop -3, push 5, push 6, pop -6, push 7, push 8, pop -8, pop -7, pop -5, pop -2, pop -1] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.
스택 선언, 오름차순으로 스택에 담기 위해 k를 선언, 문자열 출력을 위해 ans를 선언
입력한 값 num까지 1부터 차례대로 stack에 push 한다. 이 때+를 ans에 붙인다.
스택에 들어간 마지막 숫자top()가 입력한 값 num과 같다면 pop 한다. 이 때-를 ans에 붙인다.
같지 않다면 오름차순 스택으로 만들 수 없는 수열이기 때문에 "NO"를 출력한다.
💻소스코드
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
// 스택수열
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, num; // 입력
stack<int> st;
string ans;
int k = 1;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> num;
if (num >= k) { // 입력한 값 num까지 1부터 차례대로 stack에 push
while (num >= k) {
st.push(k);
k++;
ans += "+";
}
st.pop();
ans += '-';
}
else {
if (num == st.top()) {
st.pop();
ans += "-";
}
else {
cout << "NO\n";
return 0;
}
}
}
// +, - 출력
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << "\n";
return 0;
}📝17298번: 오큰수
문제 설명
오큰수
해결 방법
오큰수를 수열의 가장 마지막 원소부터 구한다.
수열의 가장 마지막 원소에 대한 오큰수는 항상 -1이다.
입력 받은 수를 넣을 v 벡터, 오큰수를 넣을 ans 벡터를 선언한다.
우선 N개의 수를 입력 받아서 v 벡터에 push_back 한다.
수열의 뒤에서부터 수를 스택에 push 한다.
stack의 top과 v의 원소들을 뒤에서부터 비교해서 top이 더 크면 오큰수이므로 stack에 남기고 그렇지 않으면 pop 한다.
위의 과정에서 스택이 비어있다면 오큰수가 없다는 의미이므로 -1을 ans 벡터에 push_back 하고, 비어있지 않다면 오큰수가 top에 있다는 의미이므로 st.top 을 push_back 한다.
ans 벡터의 뒤에서부터 출력한다.
💻소스코드
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main()
{
// 오큰수
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, A;
stack<int> st;
vector<int> v, ans;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> A;
v.push_back(A);
}
for (int i = N - 1; i >= 0; i--) {
while (!st.empty() && st.top() <= v[i])
st.pop();
if (st.empty())
ans.push_back(-1);
else
ans.push_back(st.top());
st.push(v[i]);
}
for (int i = N - 1; i >= 0; i--)
cout << ans[i] << " ";
return 0;
}