[C++][백준 1874] 스택 수열
https://www.acmicpc.net/problem/1874
제출 코드(개선 전)
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> v(n);
stack<int> s;
vector<char> res;
for (int i = 0; i < n; i++)
cin >> v[i];
int pnt = 1;
for (int i = 0; i < n; i++)
{
if (v[i] < pnt)
{
if (s.empty() || v[i] != s.top())
{
cout << "NO";
return 0;
}
s.pop();
res.push_back('-');
continue;
}
while(v[i] > pnt)
{
res.push_back('+');
s.push(pnt);
pnt++;
}
res.push_back('+');
res.push_back('-');
pnt++;
}
for (auto r : res)
cout << r << '\n';
}우선 NO를 출력해야 하는 조건에 대해서 생각해보니
1. 순서대로 1씩 증가해가는 pnt 변수보다 이번에 온 수열의 크기가 더 작고(그렇다면 무조건 해당 수는 스택 안에 존재)
2. 스택의 top이 해당 수와 일치하지 않은 경우
였다
그 외의 경우에는 계속 + 를 출력(실제로는 출력하면 안 되기 때문에 res vector에 push)하며 pnt를 1씩 증가시키다가, pnt가 이번에 위치한 수열과 일치해진다면 +와 -를 출력하고(스택에 넣었다 빼기) 수열의 다음 인덱스로 넘어간다
이때 pnt 변수보다 이번에 출력해야 하는 수가 더 작다면 위에서 말했듯 해당 수는 무조건 스택 안에 존재하기 때문에 스택의 top을 보고, 스택의 top이 이번에 출력할 수와 같다면 pop을 해주고 -를 출력한 뒤, 수열의 다음 인덱스로 넘어간다
추가적으로,
if (s.empty() || v[i] != s.top())
{
cout << "NO";
return 0;
}해당 부분에서 stack이 비어있다면 s.top에 접근하는 과정에서 오류가 발생하기 때문에 위와 같이 코드를 작성해도 되는가 찾아보았다
C++에서 단락 평가를 사용하기 때문에(목적은 최적화)
만약 || (OR 연산)에서 왼쪽 피연산자가 true라면 오른쪽 피연산자를 연산하지 않고 true를 반환하고,
&& (AND 연산)에서 왼쪽 피연산자가 false라면 오른쪽 피연산자를 연산하지 않고 false를 반환한다
따라서 s.empty()가 true라면 오른쪽의 s.top에 접근하지 않고 true를 반환하고,
s.empty()가 false여서 스택이 비어있지 않은 상태에서만 s.top에 접근하므로 오류가 나지 않는다
이후 다른 분들의 코드를 보며 개선점을 찾아보았다
1. 응답을 vector 형식 대신 string 형태에 "+\n"혹은 "-\n"을 더하는 식으로 저장해두고 출력하는 방법
2. 내 코드에서는 스택이 비어있는 여부를 체크했는데, 사실 스택을 체크해야 하는데(pnt보다 v[i]가 작은 상황) 스택이 비어 있는 상황은 생길 수 없다. 따라서 ||문으로 연결하지 않고 바로 s.top에 접근해도 문제 없다
3. +나 -를 판단하고 pnt를 증가시키는 등의 일련의 과정이 복잡한데, 좀 더 간소화할 수 있을 것 같다
4. 주어진 수열을 받을 때 vector를 선언하고 그 안에 차례로 저장하는데, 어차피 순서대로 출력하는 것이니 굳이 저장해둘 필요가 없다(처음에 문제를 잘못 이해하고 짜둔 코드를 그대로 사용하느라 벌어진 일 같다)
제출 코드(개선 후)
#include <iostream>
#include <stack>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
stack<int> s;
string res ="";
int pnt = 1;
for (int i = 0; i < n; i++)
{
int input;
cin >> input;
while(input >= pnt)
{
res += "+\n";
s.push(pnt++);
}
if (input != s.top())
{
cout << "NO";
return 0;
}
s.pop();
res += "-\n";
}
cout << res;
}
소요 시간도 절반으로 줄어들고 코드도 훨씬 간단해진 것을 확인할 수 있다
추가로 궁금해서 찾아본 게 있다
for (int i = 0; i < n; i++)
{
int input;
cin >> input;
}이 부분에서 int input을 for문 내부에 쓸 수도 있고, for문 외부에 쓸 수도 있는데 두 방법의 사이에 유의미한 차이가 있는지 궁금했다
결론적으로는 둘은 동일한 오버헤드를 갖는다고 한다