본문 바로가기
프로그래머스

[프로그래머스/C] 큰 수 만들기

by jonnwon 2024. 6. 22.
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