문제 이해 단계
https://www.acmicpc.net/problem/1874
이해하는데만 엄청 오래 걸렸던 문제 같다.
처음에 힌트가 있는 줄도 모르고
예제 케이스 입력이랑 출력 비교해 가면서 어떻게든 이해해 보려고 고생을 했다.
내가 잘못 이해했던 점은 입력으로 들어간 수열로 계산을 하는 게 아니라
입력으로 들어간 수열이 최종적으로 나오는 것이었다.
문제를 간단히 표현하면, 맨 처음 수열의 개수 n이 주어지고
스택에 1부터 n까지를 순차적으로만 넣을 수 있다.
스택에서 꺼낸 숫자는 수열에 추가된다.
이 방식으로 입력에서 넣은 수열을 만들어야 한다.
이때 이뤄지는 과정을 출력하는 건데,
push(+), pop(-)로 처리하고 만약 입력 수열을 만들 수 없다면 No를 출력한다.
문제 접근 단계
당연히 문제에서부터 스택수열이기도 해서 스택을 쓰는 것까지는 생각했다.
그리고 입력수열을 만드는 과정을 생각하며 코드를 짰다.
일단은 NO가 나오는 경우는 나중에 처리해주려고 했다.
포인트 1.
Push/pop 조건, 반복 언제까지 해야 하나?
스택 맨 위에 있는 숫자가 찾고자 하는 수와 같으면 pop, 다르면 push.
push를 했으면 스택에 넣어주는 수를 +1
pop을 했으면 찾고자 하는 수열 리스트에서 인덱스를 +1
이 과정을 스택에 n까지 넣은 후, 스택이 빌 때까지 반복하는 것이다.
이 전체적인 과정을 어떻게 구현할 것인가 하는 것이 관건이었다.
일단 입력 수열을 담을 리스트를 리스트를 하나 만들고,
정답을 담을 char형 리스트를 하나 만들었다.
그리고 1부터 순차적으로 n까지의 숫자를 담을 변수 cnt를 만들어서 비교하였다.
포인트 2.
NO가 나올 조건
포인트 1의 반복을 계속한다면,
cnt 가 (입력받은 수열의 수 + 1) 보다 작거나 같을 때까지 반복한다.
스택의 맨 위의 숫자가 입력 수열보다 같지 않으면
cnt++이기 때문에 언젠간 반복문이 끝난다.
그래서 이 조건을 이용했다.
모든 반복이 끝난 후, 마지막에 +가 출력됐다는 것은
스택이 비어있지 않다는 것을 의미하기 때문에 NO를 의미한다.
그럼 여기서 한 가지 의문이 들었다.
마지막에 -가 출력되어 스택을 성공적으로 비워지면 입력 수열을 만들 수 있음을 의미하는가?
결론은 맞다.
Pop이 될 때, cnt는 그대로이기 때문에 결국에는 매치되지 않는다면 +로 끝날 수밖에 없다.
이를 반대로 말하면 -로 끝나기 위해서는
cnt <= (입력받은 수열의 수 + 1)를 만족하면서 스택이 비어있어야 한다.
이 포인트들을 생각하면서 코드를 구현해 보았다.
문제 구현 단계
while (cnt <= num + 1) {
//스택이 비어있을 경우 (stack.top() 에러 방지)
if (stack.empty()) {
if (cnt == num + 1) break; // 모든 수가 스택에 넣었을 경우
else {
//Push
stack.push(cnt);
cnt++;
answerList.push_back('+');
}
}
//스택이 비어있지 않을 경우
else {
// 입력수열과 스택 맨 위를 비교
if (stack.top() != checkList[checkIndex]) {
stack.push(cnt);
cnt++;
answerList.push_back('+');
}
// 입력수열과 스택 맨 위가 일치하는 경우
else {
//Pop
stack.pop();
checkIndex++;
answerList.push_back('-');
}
}
}No가 나오는 경우를 제외한 반복 사이클 구조이다.
스택이 비어있을 때 stack.top()으로 맨 위의 값을 참조하려고 하니 에러가 뜬다.
이를 방지하기 위해 stack.empty()로
스택이 비어있는 경우와 그렇지 않은 경우를 나누었다.
스택이 비어있는 상태에서, cnt가 입력배열의 개수 + 1 이면
스택 안에 1부터 n까지 모두 넣었다는 것이므로 반복을 탈출한다.
이 경우에만 성공으로 간주한다. (가장 마지막에 -로 끝났기 때문)
나머지는 '아직 스택 안에 넣어야 될 수가 남아있다.'는 뜻이므로 push를 해준다.
스택이 비어있지 않은 경우에는 checkList에 입력수열을 저장해 놨는데,
일치 불일치를 확인하여 push와 pop을 판단하기 위함이다.
push를 하면 cnt++, pop을 하면
다음 입력 수열을 찾아야 하기 때문에 checkIndex++를 통해 검색해 줬다.
if (answerList[answerList.size() - 1] == '-') {
for (int i = 0; i < answerList.size(); i++)
cout << answerList[i] << "\n";
}
else cout << "NO" << "\n";NO를 색출해 내는 부분이다.
answerList에 '+' '-'를 담는 과정을 반복하는 윗 코드에서 반복이 끝난 후,
answerList의 마지막 배열이 +로 끝나는가 -로 끝나는가를 판단한다.
-로 끝나면 성공을 의미하기 때문에, answerList의 배열을 한 줄씩 출력
+로 끝나면 실패를 의미하기 때문에 NO를 호출한다.
전체코드는 아래와 같다.
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int num;
vector<char> answerList;
vector<int> checkList;
cin >> num;
for (int i = 0; i < num; i++) {
int val;
cin >> val;
checkList.push_back(val);
}
stack<int> stack;
int cnt = 1;
int checkIndex = 0;
while (cnt <= num + 1) {
//스택이 비어있을 경우 (stack.top() 에러 방지)
if (stack.empty()) {
if (cnt == num + 1) break; // 모든 수가 스택에 넣었을 경우
else {
//Push
stack.push(cnt);
cnt++;
answerList.push_back('+');
}
}
//스택이 비어있지 않을 경우
else {
// 입력수열과 스택 맨 위를 비교
if (stack.top() != checkList[checkIndex]) {
stack.push(cnt);
cnt++;
answerList.push_back('+');
}
// 입력수열과 스택 맨 위가 일치하는 경우
else {
//Pop
stack.pop();
checkIndex++;
answerList.push_back('-');
}
}
}
if (answerList[answerList.size() - 1] == '-') {
for (int i = 0; i < answerList.size(); i++)
cout << answerList[i] << "\n";
}
else cout << "NO" << "\n";
}
시행착오
위 문제는 시행착오가 정말 많은 문제였다.
전체적인 반복구조를 구현해 나가는 과정은 쉬웠지만 예외적인 부분을 처리하는데 굉장히 애를 먹었다.
그리고 구현했다 해도 코드가 지저분해서 마음에 들지 않았다.
그래서 stack.empty()를 기점으로 나눠서 생각한 게 가장 깔끔한 코드였다.
NO를 구현하는 과정이 나한테는 가장 복잡했는데,
처음에는 cnt값이 stack에 있는 수보다 클 때를 기준으로 생각하다가
예외 케이스가 너무 많이 나오기도 하고 명료하지 않아, 그 방식을 포기하고 다른 방식을 찾았다.
그 방식이 반복이 끝나고 +로 끝나는가 -로 끝나는가의 문제였다.
이 부분을 생각해 내는데 한 1~2시간이 걸렸던 것 같다.
가장 애를 먹었던 건 시간초과 부분이다.
분명 결과도 다 맞고 제대로 뜨는데 이게 시간초과가 나온다고 생각했다.
처음에는 접근을 잘못했나라는 생각으로 알고리즘을 처음부터 짜려고 했는데
아무리 생각해 봐도 이 방식이 시간초과가 뜰 정도는 아니었다.
문제는 C++언어 자체였다.
if (answerList[answerList.size() - 1] == '-') {
for (int i = 0; i < answerList.size(); i++)
cout << answerList[i] << "\n";
}
else cout << "NO" << "\n";처음에는 answerList를 출력하고 줄 바꿈을 해주는데 endl을 사용했는데,
이게 시간을 엄청 잡아먹는다더라
그래서 이를 "\n"처리를 해주니 바로 정답 처리가 떴다.
정말 짜증 나고 화가 났는데 어쩔 수 있나.
그냥 앞으로는 무조건 "\n"로 처리해 줘야겠다.
이번 문제에서 얻은 점은 C++에서는 문제 풀 때
무조건 줄 바꿈을 "\n"로 해줘야 했다는 것을 크게 느꼈다.