728x90
반응형
https://school.programmers.co.kr/learn/courses/30/lessons/42883
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
char* solution(const char* number, int k) {
int len = strlen(number) - k;
char* answer = (char*)malloc(sizeof(char) * (len + 1));
int stack = -1;
for (int i = 0; i < strlen(number); i++) {
while (k > 0 && stack > -1 && answer[stack] < number[i]) {
--stack;
--k;
}
if (stack < len - 1) {
answer[++stack] = number[i];
}
}
answer[len] = '\0';
return answer;
}
가능한 가장 큰 숫자를 만들기 위해 각 자리에서 최적의 선택을 한다. (그리디 알고리즘)
제거 후 남을 숫자의 길이를 len 으로 초기화 하여 len만큼의 stack 을 만든다. (answer)
number 문자열의 각 숫자를 순회하면서 숫자를 제거 할 수 있는 횟수 k가 양수이고, 현재 숫자가 스택의 맨 위 문자보다 크면, 스택의 맨 위 문자를 제거한다. 이는 현재 문자가 더 큰 숫자를 만들 수 있기 때문이고, 이 과정을 k가 0이 될 때까지 반복한다.
현재 순회 중인 숫자가 stack에 들어갈 자리가 있으면 스택에 현재 숫자를 추가한다. 스택의 인덱스가 반환해야 할 길이를 초과하지 않도록 한다.
728x90
'프로그래머스' 카테고리의 다른 글
[프로그래머스/C] 전력망을 둘로 나누기 (0) | 2024.06.23 |
---|---|
[프로그래머스/C] 가장 큰 수 (0) | 2024.06.22 |
[프로그래머스/C] 주식가격 (0) | 2024.06.22 |
[프로그래머스/C] 특이한 정렬 (0) | 2024.06.21 |
[프로그래머스/C] 피로도 (0) | 2024.06.20 |