/* wkfyfmf sjgsms vntldlqrndhk wkfyffm Qhqsms vkq dlqrnrk rkxdk wpdlf ajswj emfdjrks wkfyrk wpdlf skwnddp skdhsms tmxordp vntlgksms tnstjsms qksemtl dh 반드시 오름차순을 지키도록 한다고 ㅏㅂ니다. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는 지 있따면 어떤 수넛로 푸시와 팝을 연산을 수행해야 하는지 알아낼 수 있습니다. 지금 넣었다고 가정하는 겁니까? 4 3 6 8 7 5 2 1 8 6 3 4 */ #include <stdio.h> #include <iostream> using namespace std; int main() { int stack[100000]; char res[200000]; int i, n, k, stkIdx = 0, resIdx = 0, max = 0; cin >> n; while (n--) { cin >> k; if(k>max) for (i = max; i < k; i++) { stack[stkIdx++] = i + 1; res[resIdx++] = '+'; } else if (stack[stkIdx - 1] != k) { puts("NO"); return 0; } stkIdx--; res[resIdx++] = '-'; if (max < k) max = k; } for (i = 0; i < resIdx; i++) cout << res[i] << endl; return 0; } |
이거 뭐지? 문제가 뭔지 왜 이때 스택을 사용하는 것인지 한번 디버깅 모드로 하나씩 돌려봐야겠다. |
#include <stdio.h> #include <stack> #include <vector> using namespace std; int n, a[100001]; stack<int> stk; vector<char> ans; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); int pos = 0; for (int i = 1; i <= n; i++) { stk.push(i), ans.push_back('+'); while (!stk.empty() && stk.top() == a[pos]) { pos++, stk.pop(), ans.push_back('-'); } } if (!stk.empty()) puts("NO"); else for (auto it : ans) printf("%c\n", it); return 0; } |
문제가 무엇인지 알겠습니다. 일단 숫자를 모두 입력받은 다음에, 이것을 스택을 이용해서 이 수열을 만들수 있을지 없을지 결정하면 됩니다. 쌓고 넣고 쌓고 넣고 해서, 1234 쌓고 4를 빼고, 이런식으로 진행하면 됩니다. 오케이. |