문제
소스코드
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
|
#include <string>
using namespace std;
string solution(string number, int k) {
int count = k;
//K만큼 반복문을 돌며 내림차순으로 찾는다.
for (int i = 0; i < k; ++i) {
//현재와 다음을 비교해서 현재가 더 작은수라면 삭제
for (int i = 0; i < number.size() - 1; ++i) {
//다음값이 더 크니까 삭제
if (number[i] < number[i + 1]) {
//찾은 값삭제
number.erase(i, 1);
--count;
break;
}
}
}
//예외 처리 테스트 케이스(12)
if (count != 0) {
for (int i = 0; i < count; ++i) {
number.pop_back();
}
return number;
}
return number;
}
|
후기
이 문제를 해결하기 위한 키워드는 그리디이다.
이 문제는 그리디(탐욕) 알고리즘을 사용하는 문제로 나는 앞에 수와 다음수를 비교해서 다음 수가 더 크다면 지우는 방식으로 해서 문제를 풀었다. 이렇게 까지 풀면 테스트 케이스 12번을 제외하고는 다 통과를 할 수 있다.
문제는 마지막 테스트 케이스인대
"99991" , 3 여기서 answer은 99 인대 나는 91이 나와서 계속 오류가 발생해서 22~26번 줄에 예외 처리를 해서 억지 느낌으로 통과했다. 아마 테스트 케이스가 많이 허술해서 통과할 수 있던 거 같고 다른 사람의 풀이를 보면 얼마나 멍청하게 풀었는지 알 수 있는 문제였다.
출처 및 레퍼런스
문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42883
'온라인 코딩 > 그리디(Greedy)' 카테고리의 다른 글
[백준] 11047번 동전 0 (0) | 2021.02.11 |
---|---|
[백준] 5585번 거스름돈 (0) | 2020.05.17 |