728x90
https://www.acmicpc.net/problem/1874
스택 C++
처음에 문제 이해를 못해서 이해하는데 시간이 좀 걸렸다.
1부터 n까지의 수가 연속된 수라는 점을 이해하면 된다.
1부터 n까지의 수가 섞여있는 수열이 주어지고 나는 1,2,3,4,...,n 까지의 수를 순서대로 스택에 push할 수 있고
또 pop하면서 결과적으로 pop하여 만들어진 수열이 입력된 수열이 되도록 하는 것
접근방법
입력받을 수 만큼의 반복문을 돌면서 (반복문 한번에 숫자 하나씩 입력받는다.)
스택의 top과 입력받은 수(num)를 비교한다.
스택이 비었거나(초기상태 대비) top < num 이면
top에 num에 해당하는 수가 올때까지 push한다.
top == num 이면
pop한다.
그리고 top > num 이면
NO를 출력하고 프로그램을 끝낸다.
flag용 변수를 남발해서 이렇게 지저분한 코드가 없다. 하면서 제출했는데
의외로 한번에 통과돼서 기분 좋았다. 오늘은 이따 낮에 바쁠 것 같아서 지금 올려둠!
소스코드
#include <iostream>
using namespace std;
class Stack{
public:
int size;
int* stack;
Stack(int maxSize){
size = 0;
stack = new int[maxSize];
}
void push(int n){
stack[size++] = n;
}
int pop(){
if(isEmpty()){
return -1;
}
else{
return stack[--size];
}
}
int getSize(){
return size;
}
bool isEmpty(){
if(size == 0)
return true;
else
return false;
}
int top(){
if(isEmpty()){
return -1;
}
else{
return stack[size-1];
}
}
};
int main(){
int n;
cin >> n;
Stack s = Stack(n);
char result[2*n];
int cnt = 0;
int num;
for(int i = 1, a = 1 ; i <= n ; i++){
cin >> num;
while(s.isEmpty() || s.top() < num){
s.push(a++);
result[cnt++] = '+';
}
if(s.top() == num){
s.pop();
result[cnt++] = '-';
}
if(s.top() > num){
cout << "NO";
return 0;
}
}
for(int i = 0 ; i < 2*n ; i++)
cout << result[i] << "\n";
return 0;
}
728x90
'알고리즘 문제풀이' 카테고리의 다른 글
[백준 2579] 알고리즘 42일차 : 계단 오르기 (0) | 2020.08.12 |
---|---|
[백준 1932] 알고리즘 41일차 : 정수 삼각형 (0) | 2020.08.11 |
[백준 4949] 알고리즘 38일차 : 균형잡힌 세상 (0) | 2020.08.06 |
[백준 9012] 눈물겨운 알고리즘 37일차 : 괄호 (0) | 2020.08.05 |
[백준 10773] 알고리즘 36일차 : 제로 (0) | 2020.08.03 |