| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 9244 | 1808 | 1349 | 22.701% |
문제
N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)
둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.
출력
입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.
접근
어떤 수를 지웠을 때 가장 큰 수가 나오는지 종이에 적어보면서 시험해보았다.
해답은 어렵지 않았다.
그냥 순회하면서 앞의 숫자가 뒤에 숫자보다 큰 경우 지워주면 됐다.
다만, K개를 지웠을 때의 길이를 잘 고려해야 된다.
풀이
ans 벡터를 만들어서 숫자들을 저장해주었다.
숫자를 순회하면서 ans.back()이 더 작은 경우에는 빼주면서 값을 저장했다.
이 때 K 값이 0이 되면 더 이상 작업을 하지 않게 유의해줬다.
마지막까지 순회했을때 K값이 0이 아니라면, 아직 빼지 않은 숫자가 있는 것이다.
당연히 제일 뒤의 숫자가 제일 작을 것이므로, 길이를 맞춰서 출력해주었다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int N, K;
string str;
vector<char> ans;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
CIN3(N, K, str);
ans.push_back(str[0]);
FUP(i, 1, N - 1)
{
if (!K) ans.push_back(str[i]);
else
{
while (!ans.empty() && K && ans.back() < str[i])
{
ans.pop_back();
K--;
}
ans.push_back(str[i]);
}
}
for (int i = 0; i < ans.size() - K; i++)
COUT(ans[i]);
return 0;
}
Beginner