📌큰 수 만들기
/* 해당 문제 설명은 링크로 대체한다. */
📌풀이
문제를 보면 숫자에서 두 수를 제거해서 만든다고 명시되어 있는데 앞에서부터만 지울 수 있다는 건 명시되어 있지않다 ...
하지만 입출력 예시를 보면 앞에서부터 작은 수를 제거한다..... 주의하자 !
먼저 문자 수가 4자리인데 k만큼 뺀 수를 제거하면 2자리만 출력하면 된다.
그래서 for문은 number.size() - 2 한 값 만큼 돌려주었다.
그리고 for문 안에서 가장 큰 value 값을 구해서 idx 갱신하며 가장 큰 값들만 answer에 더해주었다.
이 풀이의 주의점은 for문 내 for문에서 첫번째 인덱스부터 검사해주기 위해 idx를 초기에 -1로 설정한 점이다!
📌코드
#include <string>
#include <vector>
using namespace std;
string solution(string number, int k)
{
string answer = "";
//k만큼 뺀 수만 출력
int idx = -1; //0번째 인덱스부터 검사하기 위함
for (int i = 0; i < number.size() - k; i++)
{
char maxValue = ' ';
for (int j = idx + 1; j <= k + i; j++)
{
if (maxValue < number[j])
{
maxValue = number[j]; //갱신
idx = j;
}
}
answer += maxValue;
}
return answer;
}
회고
greedy 하게 문제를 푸는 건 생각보다 어렵다.
이론 상으로 이해하는건 어렵지 않은데 문제를 greedy하게 접근하는 것은 어려운 것 같다.
'코딩테스트 공부 > Programmers' 카테고리의 다른 글
[C++] level3 이중 우선순위 큐 42628 (0) | 2021.09.05 |
---|---|
[C++] level1 체육복 42862 (0) | 2021.09.01 |
[C++] level2 구명보트 42885 (0) | 2021.09.01 |
[C++] level1 모의고사 42840 (0) | 2021.08.31 |
[C++] level2 소수 찾기 42839 (0) | 2021.08.31 |
댓글