프로그래머스 Level2_ 큰 수 만들기 (C++)

프로그래머스는 앞에서 부터 범위 내 가장 큰 값을 저장하여 앞에서 부터 추가하는 코드로 하면 잘 통과 되지만..

백준에도 똑같은 문제가 있다.

[BOJ 2812 크게만들기] : www.acmicpc.net/problem/2812

2812번: 크게 만들기

백준에 똑같이 적용하면 시간초과를 뱉는다. 

백준은 스택을 이용하여 작은수가 나오면 스택에 저장하고 큰 수가 나오면 스택을 큰게 나올때 까지 pop해준다. pop해준 갯수를 기록하고 pop해준 갯수가 K를 넘으면 빠져나오는 풀이를 적용하였다.

 

프로그래머스 큰 수 만들기 코드 :

#include <string>   // Level2_ 큰 수 만들기 [그리디]
#include <vector>

#include <iostream>
using namespace std;

string solution(string number, int k) {
    string answer = "";

    int n = number.size()-k, idx = -1;

    for(int i=0; i<n; i++){
        char max = 0;
        for (int j=idx+1; j<=k+i; j++){
            if(max < number[j]){
                max = number[j];
                idx = j;
            }
        }
        answer += max;
    }

    return answer;
}

백준 크게만들기 코드 :

#include<cstdio>	// 2812_크게만들기 [그리디] [스택]
#include<stack>
using namespace std;

int main(){
	int K, N, i;
	scanf("%d %d\n",&N, &K);

	char number[500001], answer[500001];
	scanf("%s", number);

	stack<char> s; int poped=0;
	s.push(number[0]);

	for(i=1;i<N && poped<K; i++){
		if(s.top() >= number[i]){
			s.push(number[i]);
		}
		else{
			while(!s.empty() && s.top() < number[i] && poped < K){
				poped++;
				s.pop();
			}
			
			s.push(number[i]);
		}
	}
	while(poped < K){
		s.pop();
		poped++;
	}
	int l = s.size();
	for(int j=0; j<N-K; j++){
		if(!s.empty()){
			answer[l-j-1] = s.top();
			s.pop();
		}
		else{
			answer[j] = number[j+K]; 
		}
	}
	printf("%s\n", answer);
	return 0;
}