[프로그래머스] 큰 수 만들기 C++ 풀이 및 해설

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

 

풀이 방법

내 풀이 방법보다 다른 풀이 방법 코드가 깔끔해보여서 두가지 풀이 방법을 소개한다.

 

(1) 내 풀이

스택에는 항상 큰 숫자가 아래에 있고 점점 작은 숫자가 위에 쌓이게 상태를 유지한다.

 

numbers 문자를 하나씩 탐색하며

현재 numbers 문자보다 스택의 top이 작다면 pop을 반복해준다.

그리고 numbers 문자를 무조건 push한다.

이 과정을 numbers 문자 모두를 반복한다.

그러나 현재까지 만들어 놓은 큰 숫자 문자열인 스택과 남은 문자열을 모두 더해야지만 answer의 길이를 맞춰줄 수 있다면

반복하지 않고 남은 문자열들을 모두 더해 answer을 찾는다.

 

이 로직은 987654321 같은 케이스가 주어졌을때 무조건 push에 의해

스택에 answer의 길이가 고려되지 않고 모두 들어가버리는 경우가 있다.

그래서 위의 스택 로직을 수행한 후 길이에 맞게 pop을 해주는 과정이 필요하다.

 

(2)

검색하면 많이 나오는 풀이 코드이다.

https://born2bedeveloper.tistory.com/27 이해하기 좋은 설명이고

https://ansohxxn.github.io/programmers/kit22/ 위의 설명의 이해를 더해줄 그림이 잘되어있다.

 

안쪽 for문의 k+i가 이해가 제일 안갔는데 두번째 링크의 그림부분에 민트색으로 칠해놓은 부분의 범위를 보고 이해했다.

i는 현재까지 뽑은 숫자의 개수이다.

i가 증가함에따라 뒤에 보장될 최소의 숫자들이 줄어듬을 뜻한다.

쉽게, 그림 설명 부분에 민트색을 칠해놓은 부분의 end가 한개의 큰 숫자를 뽑을때마다 뒤로 한칸씩 밀려나는게 보인다.

그래서 k+i인것이다. 뒤로 i칸씩 범위가 밀려난다.

 

전체 코드

(1)

#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;

string solution(string number, int k) {
    string answer = "";
    stack<char> s;
    int len = number.length();

    s.push(number[0]);
    int idx=1; 
    // len-idx는 현재 idx위치를 포함하여 몇개의 숫자가 남았는지
    // len-k는 만들어야하는 answer의 길이
    while(1) {
        
        // pop하기전에 pop을하고 뒤에 남은 숫자들로 len-k를 만들 수 있는지 체크한다.
        // len-idx에 현재까지 만든 문자열 size를 더하면 현재 만들 수 있는 제일 긴 길이이다.
        // 이것이 len-k보다 크다면 pop을해도 남은 숫자들로 만들 수 있는 상태가 보장된다.
        while(!s.empty()&&s.top()<number[idx]&&s.size()+len-idx>len-k) {
            s.pop(); // 현재 숫자보다 작은 숫자라면 계속 팝을 해준다.
        }
        
        s.push(number[idx]); // 현재 문자 무조건 푸쉬.
        idx++;
                
        if(s.size()+len-idx==len-k) { // 현재까지 만든 문자열 size와 남은 문자열을 더한게 만들어야하는 answer과 일치하면
            break;
        }
    }
    
    // 위의 로직은 현재 문자를 크기비교pop연산 후에 무조건 푸쉬하기에
    // 987654321에서 k=2일때 9876543에서 계속 push하여 스택에 987654321이 들어갈 수 있다.
    while(!s.empty()&&s.size()>len-k) { // 뒤늦은 문자들을 pop해준다.
        s.pop();
    }
    
    // idx가 끝까지 안간 경우 처리이다.
    // s.size()+len-idx>len-k에서 참이되지 않아. 즉, 남은 문자열을 모두 써야지 길이를 맞출 수 있는 상황이다.
    // 남은 문자들을 스택에 넣어준다.
    for(;idx<number.length();idx++) { 
            s.push(number[idx]);
    }
    
    while(!s.empty()) { // 스택에 문자들을 꺼내 답에 추가하고
        answer+=s.top();
        s.pop();
    }
    
    // 스택을 이용했으므로 거꾸로 답이 들어가 있다. answer을 한번 뒤집어주자.
    reverse(answer.begin(), answer.end());
    return answer;
}

 

(2)

#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;

string solution(string number, int k) {
    string answer = "";
    
    int cur = 0;
    for(int i=0; i<number.length()-k; i++) {
        char maxNum = number[cur];
        int maxIdx = cur;
        for(int j=cur; j<=k+i; j++) {
            if(maxNum<number[j]) {
                maxNum=number[j];
                maxIdx=j;
            }
        }
        cur = maxIdx+1;
        answer += maxNum;
    }
    return answer;
}