반응형
https://www.acmicpc.net/problem/2812
2812번: 크게 만들기
N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
[ 문제풀이 ]
1. stack에 가장 첫 번째 숫자를 넣습니다.
2. 이후 for문을 돌면서 stack.top()과 arr [ i ]를 비교합니다.
3. stack.top() < arr [ i ] 이면 stack.top() >= arr [ i ]가 될 때까지 stack.pop()을 해줍니다.
4. 이후 stack에 arr [ i ]를 push 해줍니다.
5. ans에 stack에서 하나씩 뽑아 저장해 준 후 for문을 돌면서 하나씩 출력해줍니다.
[ 소스코드 ]
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 | #include<iostream> #include<stack> using namespace std; int N, K; char arr[500001]; int main() { scanf("%d %d", &N, &K); scanf("%s", arr); stack<int> s; stack<int> ans; s.push(arr[0] - '0'); int cnt = 0; for (int i = 1; i < N; i++) { while (!s.empty()) { if (s.top() < arr[i] - '0' && cnt < K) { s.pop(); cnt++; } else break; } s.push(arr[i] - '0'); } while (!s.empty()) { ans.push(s.top()); s.pop(); } for (int i = 0; i < N - K; i++) { printf("%d", ans.top()); ans.pop(); } } | cs |
반응형
'백준' 카테고리의 다른 글
[ 백준 ] 1365번 - 꼬인 전깃줄 (C++) (0) | 2022.12.16 |
---|---|
[ 백준 ] 16397번 - 탈출 (C++) (0) | 2022.12.15 |
[ 백준 ] 9019번 - DSLR (C++) (0) | 2022.12.13 |
[ 백준 ] 2665번 - 미로만들기 (C++) (0) | 2022.12.12 |
[ 백준 ] 1726번 - 로봇 (C++) (0) | 2022.12.11 |