알고리즘/백준 BAEK JOON
1874.스택 수열
IMyoungho
2020. 4. 2. 23:59
이 문제는 그렇게 어려운 문제는 아니였지만 굉장히 헷갈리긴 했다.
Stack과 Queue문제를 꽤 풀어본 것이 도움이 되었던 것 같다.
스택과 큐에 대한 다른문제들도 풀었지만 난이도가 너무 쉽다고 느껴 굳이 남기지 않았다.
하지만 처음에 문제를 거꾸로 이해해버렸고 반례를 만나서야 잘못 이해했다는 것을 알아챘다.
아직 반례를 생각해 내는 것이 굉장히 서툰 것 같다..
어쨌든 결과적으로 다 구현하고 나서 시간초과가 났는데 그러한 이유는 아래와 같다.
< Code 설명 >
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int main()
{
queue<char>ans; // 부호정답이 저장될 queue
queue<int> q; // 입력받을 queue
stack<int> t; // 수열이 가능한지 쌓이는지 확인하는 stack
int num; // 수의 갯수
cin >> num; // 입력
int tmp; // 입력받기위함
for(int i=0; i<num; i++){
cin >> tmp; // 입력받아서
q.push(tmp);// queue에 저장
}
for(int i=1; i<=num; i++){ // 1부터 num까지 순차적으로 넣음
t.push(i); // 스택에 넣고
ans.push('+'); // 넣었다면면 정답 queue에 '+'도 같이 넣어줌
if(q.front()==t.top()){ // 만약 넣던중 queue의 첫번째와 stack의 top이 같다면
while(!t.empty() && q.front()==t.top()){//stack의 top과 queue의 앞이
//같은게 있는지 계속 pop하며 확인
t.pop(); // 있다면 stack에서 pop으로 제거
q.pop(); // queue역시 pop해서 다음 것 확인
ans.push('-');
}
}
if(i==num && !q.empty()){ //끝까지 탐색이후에도 입력 queue가 비어있지 안다면
while(!q.empty()){
t.push(q.front()); //나머지 queue값을 queue가 빌 때까지stack에 넣음
ans.push('-'); //큐에서 빼서 스택에 넣으므로 '-'
q.pop(); //다음 것도 넣어야하므로 pop
}
}
}
if(t.size()==q.size()) // 가능한 수열이라면 처음 입력받은 큐와 stack의 길이가 같음
while(!ans.empty()){ // 부호 queue내용 출력
cout << ans.front() << "\n";
ans.pop();
}
else{ // 비정상이라면 "NO"출력
cout <<"NO\n";
}
return 0;
}
반드시 알아야할 TIP!!
15552번: 빠른 A+B
첫 줄에 테스트케이스의 개수 T가 주어진다. T는 최대 1,000,000이다. 다음 T줄에는 각각 두 정수 A와 B가 주어진다. A와 B는 1 이상, 1,000 이하이다.
www.acmicpc.net
-> 절 때까먹지 말자!! 나는 C++을 쓰니까 되도록이면 "endl" 대신 "\n"'를 쓰는 걸 습관화 해야겠다.
반응형