문제 URL : https://www.acmicpc.net/problem/2812
2812번: 크게 만들기
문제 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000) 둘째 줄에 N자리 숫자
www.acmicpc.net
문제접근법:
꽤 고민했던 문제입니다.
처음 이중 for문으로 풀다가 당연히 시간초과 일걸생각했지만 역시나 시간초과
줄이는 방법을 생각했어야했습니다.
vector를 이용해야했고 문자를 k개를지워야하는데
반드시 지울 필요는 없다는것을 알아냈던거죠 출력을 n-k개를 출력을 하면되는거니까
벡터에 s[i](0<=i<n)를 집어넣고 s[i]가 vector에 맨 뒤에 있는 자리수보다 크면 최대 k까지 지워주면 되는것입니다.
그럼 소스코드를 보여드리겠습니다.
|
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
|
//by 콩순이 냉장고 백준 2812 크게만들기
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int k, n;
string s;
void input()
{
cin >> n >> k;
cin >> s;
}
int main(){
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
input();
vector<char> v;
int k2 = k;
for (int i = 0; i < n; i++)
{
while (v.size()&&k2&&v.back() < s[i]){//맨뒤에있는 벡터가 s[i]가크면 계속 pop시켜줌 최대 k개까지
v.pop_back();
k2--;
}
v.push_back(s[i]);
}
for (int i = 0; i < n-k; i++)//출력은 n-k개까지만 출력해주는게
{
cout << v[i];
}
cout << "\n";
}
|
cs |
질문은 언제나 환영이니 모르는 점이나 궁금한점있다면 언제든지 댓글을 이용해주시길 바랍니다.
'백준' 카테고리의 다른 글
| 백준 1707 이분그래프 (0) | 2020.07.26 |
|---|---|
| 백준 17835 면접보는 승범이네 (0) | 2020.07.26 |
| 백준 1890 점프 (0) | 2020.07.22 |
| 백준 17830 이진수씨의 하루 일과 (0) | 2020.07.22 |
| 백준 2630 색종이 만들기 (0) | 2020.07.20 |
