BOJ - 1874 - 스택 수열
문제
문제 개념
- 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다.
- n = 8
- 기준 수열 : [ 1 2 3 4 5 6 7 8 ]
- n = 8
- 스택에 push하는 순서는 반드시 오름차순을 지킨다.
- 엇갈리면 안된다.
- 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다.
- 임의의 수열 : [ 4 3 6 8 7 5 2 1 ]
- 계산결과 : + + + +, - -, + +, -, + +, - - - - -
- 임의의 수열 : [ 4 3 6 8 7 5 2 1 ]
구현 - vector 사용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main()
{
int num;
vector<int> OrderStack; // 입력스택
vector<int> NumQueue; // 기준 큐
stack<int> TmpStack; // 임시스택
vector<string> answer; // 정답스택
cin >> num;
for(int i=1; i <= num; i++)
{
int tmp;
cin >> tmp;
// 4 3 6 8 7 5 2 1
OrderStack.push_back(tmp);
// 1 2 3 4 5 6 7 8
NumQueue.push_back(i);
}
for(int i=0; i < OrderStack.size(); i++)
{
while(1)
{ // 스택의 상단과 인풋값이 맞을때 까지
if(TmpStack.empty() || TmpStack.top() != OrderStack[i])
{
TmpStack.push(NumQueue[0]);
if(!NumQueue.empty())
NumQueue.erase(NumQueue.begin());
else
break;
answer.push_back("+");
}
else if(TmpStack.top() == OrderStack[i])
{
TmpStack.pop();
answer.push_back("-");
break;
}
}
}
if(!TmpStack.empty())
{
answer.clear();
answer.push_back("NO");
}
for(auto el : answer)
cout << el << '\n';
}
구현 - stack queue lib 사용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
// 입력 저장 스택
// 기본 N까지의 수열스택
// 임시로 담아둘 스택
// 정답에 입력할 스택
int main()
{
int num;
queue<int> OrderQueue; // 입력 큐
queue<int> NumQueue; // 기준 큐
stack<int> TmpStack; // 임시스택
vector<string> answer; // 정답스택
// 수열 스택 입력
cin >> num;
for(int i=1; i <= num; i++)
{
int tmp;
cin >> tmp;
// 4 3 6 8 7 5 2 1
OrderQueue.push(tmp);
// 1 2 3 4 5 6 7 8
NumQueue.push(i);
}
for(int i=0; i < num; i++)
{
while(!OrderQueue.empty())
{ // 임시스택이 비어있을경우나 스택의 상단과 인풋값이 맞을때 까지
if(TmpStack.empty() || TmpStack.top() != OrderQueue.front())
{ // TmpStack : 1 2 3 4
TmpStack.push(NumQueue.front());
// NumQueue : 5 6 7 8
if(!NumQueue.empty())
NumQueue.pop();
else
break;
answer.push_back("+");
}
else if(TmpStack.top() == OrderQueue.front())
{ // TmpStack : 1 2 3 [4].. pop
TmpStack.pop();
answer.push_back("-");
OrderQueue.pop();
break;
}
}
}
if(!TmpStack.empty())
{
answer.clear();
answer.push_back("NO");
}
for(auto el : answer)
cout << el << '\n';
}
결과
SOL
- 입력큐에 임의의 수열 입력 & 기준 큐 생성
- 입력 큐 : [ 4 3 6 8 7 5 2 1 ]
- 기준 큐 : [ 1 2 3 4 5 6 7 8 ]
- 임시스택의 top 입력큐의 front 값과 다르면
- 같을 때 까지 기준큐 pop & 임시 스택에 기준 큐 값 push
- 정답 스택 입력 … ‘ + ’
- 같을 때 까지 기준큐 pop & 임시 스택에 기준 큐 값 push
- 임시스택의 top 입력큐의 front 값과 같으면
- 다를 때 까지 임시스택 pop & 입력 큐 pop
정답 스택 입력 … ‘ - ‘
즉. ‘ - ‘ 는 임의의 수열의 원소가 처리 되었다는 뜻 !
- 다를 때 까지 임시스택 pop & 입력 큐 pop
Work flow
n = 8
임의의 수열 : [ 4 3 6 8 7 5 2 1 ]
기준 수열 : [ 1 2 3 4 5 6 7 8 ]
임시 수열 : [ ]
- 임의의 수열의 원소 [ 4 ]
- 기준 수열 : [ 5 6 7 8 ] … 1 2 3 4 pop - queue
- 계산결과 ‘ + + + + ’
- 임시 수열 : [ 1 2 3 4 ] … 1 2 3 4 push - stack
- 임의의 수열의 원소 [ 4 ]와 임시수열 top 값과 같음.
- 임시수열 : [ 1 2 3 ] … 4 pop - stack
- 계산결과 ‘ - ’
- 임시수열 : [ 1 2 3 ] … 4 pop - stack
- 임의의 수열의 원소 [ 4 ]와 임시수열 top 값과 같음.
- 기준 수열 : [ 5 6 7 8 ] … 1 2 3 4 pop - queue
알게된 점
vector로 stack이나 queue를 구현하는 것 보다 라이브러리를 이용하는게 훨씬 계산 속도가 빠르다.