[프로그래머스] 큰 수 만들기(Greedy)

큰 수 만들기

문제설명

K만큼 문자열의 숫자를 지워서 가장 큰 수를 만든다.
number 문자열을 통해 input이 정해진다.
K개의 수를 지워서 number의 순서 변환 없이 가장 큰 수를 만들어내야한다.

첫 시도!!

처음에는 가장 작은 수 들을 지워서 만들면 된다고 생각했는데, 그런 경우에는 자리수를 고려하지 않아서 가장 큰 수가 생기지 않는다. 따라서 앞부터 수를 읽으면서 가장 큰 수를 찾아서 답을 만드는 방식으로 진행해야한다.

#include <string>
#include <vector>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <stack>
using namespace std;

string solution(string number, int k) {
    string answer=""; 
    int remainder=number.size()-k;
    int temp=0;
    int index=0;
    string copy(number);
    while(remainder)
    {
        int max=-1;
        for(int i=temp; i<= number.size()-k;i++)//최댓값을 찾는 연산
        {
            if(number[i]=='!')
                continue;
            if(max==9)
                break;
            if(max<number[i]-'0')
            {
                max=number[i]-'0';
                temp=i;
            }           
        }
        if(temp+remainder-1<number.size())//현재의 선택을 골라도 수의 길이를 맞출 수 있는지 판단
        {           
            answer+=number[temp]; 
            temp+=1;
            index=temp;
            k--;
            remainder--;
            if(number.compare(copy)!=0)
            {
                number.clear();//!로 바뀐 부분때문에 초기화
                number=copy;
            }
        }
        else//고를 수 없는 경우 비교 대상에서 제외
        {
            number[temp]='!';
            temp=index;
        }       
    }    
    return answer;
}

---

처음에는 위의 코드처럼 작성했는데, 시간초과 문제가 일어난다.

검색해보니 주로 STACK을 이용하면 시간초과가 발생하지 않는다는 것을 알게 되었다.

따라서 스택을 활용하여 코드를 다시짰다.

정확하게 어디서 오래걸리는지는 파악하지못했는데 그냥 STACK에쌓고 맨 위를 읽는 방식으로 변경하니 제대로 풀렸다.

#include <string>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <stack>
#include <algorithm>
using namespace std;

string solution(string number, int k) {
    string answer=""; 
    int remainder=number.size()-k;//총 구해야하는 숫자의 자리수
    int index=0;
    stack<char> s;

    for(int i=0; i<number.size();i++)//number를 돌면서 값을 읽고 현재 존재하는 stack의 가장 위의 값과 비교
    {
        char temp=number[i];
        while(!s.empty() && k>0)
        {
            if(s.top()<temp)//읽은 값이 stack의 가장 나중에 들어온 값과 비교해서 더 작으면 그 값은 제외
            {
                s.pop();
                k--;//숫자를 지웠으니 감소
            }
            else //그 값이 작거나 같으면 더이상 연산을 진행할 필요 없음 -> 작은 수는 들어올 필요 x
                break;
        }
        s.push(temp);
    }

    while(s.size() != remainder)//비교가 끝난 뒤 구하고자 하는 것보다 더 많이 들어왔으면 필요없는 값이므로 지움
        s.pop(); 

      while(!s.empty()){ //답 넣기 
        answer += s.top();
        s.pop();
    }

   reverse(answer.begin(), answer.end()); 

    return answer;
}

---

stl을 활용하는데 익숙해질 필요가 있다고 몸소느낀 예제였다.

시간초과는 아마도 중첩 반복문내에서 연산을 줄이는 필요가 있을 것 같다