[백준 1874] 스택 수열
백준 1874번 - 스택 수열
❓ 문제
스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.
예제 입력 1
8
4
3
6
8
7
5
2
1
예제 출력 1
+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-
예제 입력 2
5
1
2
5
3
4
예제 출력 2
NO
✏️ 풀이
Stack을 이용하라고 나와있는 문제이다.
이 문제는 스택을 이용하면 간단히 풀 수 있는 문제이다.
처음엔 조건문을 많이 넣어서 메모리 초과가 떴는데, 다시 생각해보니 조건문이 많이 필요없는 문제였다.
예제 1을 예시로 들어보자.
count=1
입력 : 4
stack에 4까지 쌓임 (입력된 숫자와 count가 같아지도록)
stack.push(count++)이기 때문에 count=5임
stack [1 2 3 4]
result [+ + + + ]
count 5
그 후 pop이 일어남
stack [1 2 3]
result [+ + + + -]
count 5
입력 : 3
stack.top()과 입력이 같음. pop 수행
stack [1 2]
result [+ + + + - -]
count 5
입력 : 6
count와 입력이 같아지도록 반복하며 stack.push(count++)
stack [1 2 5 6]
result [+ + + + - - + +]
count 7
그후 pop
stack [1 2 5]
result [+ + + + - - + + -]
입력 : 8
또 count==입력까지 반복
stack [1 2 5 7 8]
result [+ + + + - - + + - + +]
count 7
하고 pop
stack [1 2 5 7]
result [+ + + + - - + + - + + -]
이제부턴 빠르게 작성하겠다.
입력 : 7
stack [1 2 5]
result [+ + + + - - + + - + + - -]
입력 : 5
stack [1 2]
result [+ + + + - - + + - + + - - -]
입력 : 2
stack [1]
result [+ + + + - - + + - + + - - - -]
입력 : 1
stack []
result [+ + + + - - + + - + + - - - - -]
이해는 되었을 것이다.
이제 위의 과정을 코드로 작성하면 된다.
처음 접근:
- count = 1
- input 값을 받고 count > input일 때, count == input, count < input일 때를 전부 생각
- 그리고 저 조건문 안에서도 stack.empty()일 때, input과 stack.top()의 조합이 맞지 않아 예외처리가 날 때
- 등 많은 조건들을 달아주었다.
- 위와 같이 코드를 짰을 때 테스트 케이스는 통과했지만, 메모리 초과가 떴다.
조건문을 줄여야겠다고 생각하였고, 돌아가는 반복문도 줄여야 했다.
아마, 이미 스택 수열이 되지 않는 부분에서 불필요한 반복문을 더 돌아서 초과가 뜬 것 같다.
아래는 처음 짰던 함수이다.
bool make_arr(int temp) {
if (stack_arr.empty()) {
if (count > temp)
return false;
while(1) {
stack_arr.push(count);
result.push_back('+');
if (count++ == temp) {
stack_arr.pop();
result.push_back('-');
return true;
}
}
}
if (stack_arr.top() == temp) {
stack_arr.pop();
result.push_back('-');
}
else if (stack_arr.top() > temp) {
while (1) {
if (stack_arr.empty())
return false;
if (stack_arr.top() == temp) {
stack_arr.pop();
result.push_back('-');
return true;
}
else {
stack_arr.pop();
result.push_back('-');
}
}
}
else if (stack_arr.top() < temp) {
while(1) {
stack_arr.push(count);
result.push_back('+');
if (count++ == temp) {
stack_arr.pop();
result.push_back('-');
break;
}
}
}
return true;
}
다음 접근:
- count = 1
- input 값을 받고 count <= input이라면 두 값이 같아질 때까지 stack에 push
- push할 때 ‘+’ 기호를 vector에 넣어준다.
- 만약 위 2번의 케이스가 아니라면,
- stack.top() == temp라면 pop하고 ‘-‘기호를 vector에 넣는다.
- 만약 5번의 케이스가 아니라면 return false를 한다.
여기서 5번이 중요했다.
위의 코드에서는 5번도 while문으로 stack.top()과 temp가 같아질때까지 반복문을 계속 돈다.
하지만 5번의 경우, 한 번의 체크로도 스택 수열이 YES인지 NO인지 판단이 가능하기 때문에 불필요한 작업이었다.
바뀐 코드로 제출을 하니 성공하였음.
아래는 바뀐 함수
한 눈에 봐도 line 수도 줄고 불필요한 혹은 중복되는 코드들이 삭제된 것을 볼 수 있다.
bool make_arr(int temp) {
if (count <= temp) {
while(1) {
stack_arr.push(count);
result.push_back('+');
if (count++ == temp) {
stack_arr.pop();
result.push_back('-');
return true;
}
}
}
else {
if (stack_arr.top() == temp) {
stack_arr.pop();
result.push_back('-');
return true;
}
else
return false;
}
}
✔️ 정답 코드
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
stack<int> stack_arr;
vector<char> result;
int count = 1;
bool make_arr(int temp);
int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, check=0;
cin >> n;
for (int i=0; i<n; i++) {
int temp;
cin >> temp;
if (!make_arr(temp)) {
cout << "NO";
return 0;
}
}
for (int i=0; i<result.size() ; i++)
cout << result[i] << "\n";
return 0;
}
bool make_arr(int temp) {
if (count <= temp) {
while(1) {
stack_arr.push(count);
result.push_back('+');
if (count++ == temp) {
stack_arr.pop();
result.push_back('-');
return true;
}
}
}
else {
if (stack_arr.top() == temp) {
stack_arr.pop();
result.push_back('-');
return true;
}
else
return false;
}
}
Leave a comment