문제
스택 수열 백준 1874번
리뷰
문제 맨 밑에 '힌트'를 읽고 이해 했다.
1부터 n 까지 수에 대해서는 반드시 push n번, pop n번이 수행되야 목표수열을 얻을 수 있다.
만약, 스택에 숫자가 남아있으면, 실패니까 "NO" 를 출력해야 한다.
1부터 n 까지 수를 차례로 push 한다.
for(i=1; i<=num; i++){ // 1 부터 n 까지 수는 반드시 들어온다.
st.push(i);
answer.push_back('+');
}
그러나 pop을 하려면 스택의 top이 목표수열의 숫자와 일치하는지 계속 확인해줘야 한다. 그래서 while문으로 만들었다.
pop을 할 때는 목표 수열의 다음숫자를 타겟으로 해야하니까 목표수열의 인덱스도 증가시켜줘야 한다는게 중요하다.
스택이 비어있으면 pop도 불가하니까, empty() 함수로 스택이 비었는지 확인한다.
for(i=1; i<=num; i++){ // 1 부터 n 까지 수는 반드시 들어온다.
st.push(i);
answer.push_back('+');
while(!st.empty() && (st.top() == N[idx])){ // 수열의 숫자와 같으면, pop
st.pop();
answer.push_back('-');
idx++; // 목표 수열의 인덱스도 증가시켜준다.
}
}
예를 들어, 입력받은 수열크기는 8이다. 목표 수열은 4 3 6 8 7 5 2 1 이다.
목표 수열은 4 3 6 8 7 5 2 1 이다. (현재는 idx = 0, N[idx] = 4 를 타겟으로 한다. )
1, 2, 3, 4 순으로 push 했다. (위의 코드로 보면 i가 4까지 진행된 상태다)
여기서 목표수열의 첫번째 숫자 4와 스택의 top 4 가 같아진다. 즉, while 문의 조건을 충족한다.
pop 한다.
목표수열의 다음 숫자 3 과 스택의 top 3이 또 같아진다.
(idx = 1로 바뀌면서 N[idx] = 3 이 된다. )
pop 한다.
다시 5, 6 순으로 push 한다.
while 문의 조건을 다시 확인한다.
**코드
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
int N[100001]; // 입력받은 수열
vector<char> answer; // 출력할 +, - 담을 벡터
stack<int> st;
int main(void){
freopen("input.txt", "rt", stdin);
int i, idx, num = 0;
scanf("%d", &num); // num 이하의 수열을 입력받자.
for(i=0; i<num; i++){ // 목표 수열 입력받기
scanf("%d", &N[i]);
} // 입력받기 끝
// answer에는 push 할 때 '+'를 넣고, pop 할 때 '-'를 넣는다.
for(i=1; i<=num; i++){ // 1 부터 n 까지 수는 반드시 들어온다.
st.push(i);
answer.push_back('+');
while(!st.empty() && (st.top() == N[idx])){ // 수열의 숫자와 같으면, pop
st.pop();
answer.push_back('-');
idx++; // 목표 수열의 인덱스도 증가시켜준다.
}
}
if(!st.empty()) printf("NO"); // 스택에 뭐가 남았다면 실패니까 "NO"
else{
for(i=0; i<answer.size(); i++){ // answer 에 담았던 문자들 순차출력
printf("%c\n", answer[i]);
}
}
return 0;
}