프로그래머스 문제 풀이 큰 수 만들기

이 문제는 이시윤 강사님의 프로그래머스 강좌 "파이썬을 무기로, 코딩테스트 광탈을 면하자!"를 보고 정리한 내용입니다.

문제 URL 큰 수 만들기

Contents

1. 문제 지문 파악하기
2. 강사님의 알고리즘 풀이
3. 구르미의 알고리즘 풀이

문제 지문 파악하기

문제에 따르면, 입력 numbers에 대해서 해당 문자열이 가장 큰 수를 만들게끔 k개를 빼야 합니다. 예제 입력을 살펴보죠.

 

numbers = "4177252841" k = 4

 

어떻게 가장 큰 수를 만들 수 있을까요? 먼저, 일단 숫자가 나오면 저장합니다. 그리고 그 보다 큰 숫자가 나오면 저장했던 수를 빼보면 어떨까요? 자 시작해봅시다. 처음 숫자인 4를 넣습니다.

 

collected = ["4"] ( k = 4 )

 

그 후 1을 넣습니다. 1은 4보다 작기 때문에 뺄 필요가 없지요.

 

collected = ["4", "1"] ( k = 4 )

 

이제 7을 넣습니다. 그런데, 7은 마지막으로 저장된 1 보다 큽니다. 1을 빼줍니다.

 

collected = ["4"] ( k = 3 )

 

다시 collected에 저장된 마지막 수 4와 7을 비교합니다. 역시 7이 더 크니 4를 빼줍니다.

 

collected = [] ( k=2 )

 

이제 비교할 수 가 없으니 7을 넣습니다.

 

collected = ["7"] ( k=2 )

 

이제 다시, 7, 2 를 순서대로 넣습니다. 

 

collected = ["7", "7", "2"] ( k = 2 )

 

이제 5를 넣습니다. 이때, 이전에 마지막으로 저장되었던 2는 5보다 작습니다. 따라서 빼줍니다.

 

collected = ["7", "7"] ( k = 1 )

 

이제 마지막으로 저장된 7보다 작기 때문에 빼지 않고 5를 넣습니다.

 

collected = ["7", "7", "5"] ( k = 1 )

 

이제 2를 넣습니다. 마지막으로 저장된 5보다 작기 때문에 빼기는 일어나지 않습니다.

 

collected = ["7", "7", "5", "2"] ( k = 1 )

 

이제 8을 넣습니다. 이 때 이전에 마지막으로 저장된 2보다 큽니다. 따라서 2를 빼줍니다.

 

collected = ["7", "7", "5"] ( k = 0 )

 

물론 8 이전에 저장된 5 역시 8보다 작지만, 이제 더 이상 뺄 k가 없기 때문에, 8을 넣어줍니다.

 

collected = ["7", "7", "5", "8"] ( k = 0 )

 

이제 k=0 이기 때문에 뒤에 숫자들을 모두 넣어주면 됩니다.

 

collected = ["7", "7", "5", "8", "4", "1"] ( k = 0 )

 

이 문자열들을 하나로 합쳐줍니다. 그럼 원하는 결과가 나옵니다.

 

result = "775841"

 

예를 한 번 더 살펴봅시다. 다음 입력이 있다고 가정해봅시다.

 

numbers = "54321" k = 2

 

5를 넣죠

 

collected = ["5"] ( k = 2 )

 

4를 넣습니다. 마지막으로 저장된 5보다 작기 때문에 빼기는 일어나지 않습니다.

collected = ["5", "4"] ( k = 2 )

 

numbers를 모두 순회해도 앞 수보다 작기 때문에 결국 이렇게 됩니다.

 

collected = ["5", "4", "3", "2", "1"] ( k = 2 )

 

k 가 남았을 때는 collected에서 뒤부터 k개만큼 잘라주면 됩니다.

 

collected = ["5", "4", "3"] ( k = 0 )

 

즉 답은 이렇게 됩니다.

 

result = "543"

이런식으로 풀어도 되는 이유는 "앞자리 숫자가 가장 큰 수가 큰 수"이기 때문입니다. 뭔 뜬금없이 당연한 소리야?라고 하실지 모르겠습니다. 문자열 어느 부분을 쪼갠다 하더라도, 앞자리가 높은 수가 되게끔 뽑으면, 무조건 높은 숫자가 된다는 것이죠. 즉, "앞자리를 최고 큰 수로 만들기 전략"이 부분해를 만족함과 동시에 전체의 해가 될 수 있는 것이지요.

강사님의 알고리즘 풀이

강사님의 알고리즘을 순서대로 표현하면 다음과 같습니다.

 

1. 큰 수를 만드는 문자들을 모으는 배열 collected를 생성합니다.
2. number를 다음과 같이 순회합니다.
   1. 아래 조건을 만족시키면 다음을 순회합니다.
      1. 조건
         1. collected에 원소가 있어야 한다.
         2. 마지막 원소가 순회 수 num보다 작아야 한다.
         3. k가 0보다 커야 한다.
      2. collected의 가장 맨 뒤의 원소를 제거합니다.
      3. k를 1 줄입니다.
   2. k가 0이라면 numbers 인덱스 i부터 끝까지 collected에 이어 붙이고 반복문을 탈출합니다.
   3. 순회 수 num을 collected 맨 뒤에 넣습니다.
3. 만약 k가 0보다 크다면 collected를 뒤에서 k개 자릅니다.
4. collected를 이어 붙여 하나의 문자열로 만듭니다.

코드로 표현하면 다음과 같습니다.

 

def solution(number, k):
    collected = []

    for (i, num) in enumerate(number):
        while collected and collected[-1] < num and k > 0:
            collected.pop()
            k -= 1
        
        if k == 0:
            collected += number[i:]
            break

        collected.append(num)

    collected = collected[:-k] if k > 0 else collected
    answer = "".join(collected)
    return answer

 

이 알고리즘의 시간 복잡도는 O(N)입니다.

구르미의 알고리즘 풀이

저도 강사님과 비슷한 방식으로 풀었습니다. 대신 저는 스택을 이용하여 풀었습니다. 제가 세운 알고리즘은 다음과 같습니다.

 

1. 스택을 생성합니다.
2. number를 다음과 같이 순회합니다.
   1. 스택의 원소가 있고 k가 0보다 크다면 다음을 반복합니다.
   2. 스택에 순회 수 elem을 집어넣습니다.
3. k가 0이 될때까지 다음을 반복합니다.
   1. 스택에서 가장 위의 데이터를 뺍니다.
   2. k를 1 줄입니다.
4. 그렇게 해서 만들어진 스택을 하나의 문자열로 만들어줍니다.

이렇게 보니까 별반 다를게 없는 방식이네요. 파이썬 코드는 다음과 같습니다.

 

def solution(number, k):
    # 1. 스택 생성
    st = []

    # 2. 큰 수가 앞자리가 되게끔 스택에 저장합니다.
    for elem in number:
        while st and st[-1] < elem and k > 0:
            st.pop()
            k -= 1

        st.append(elem)

    # 3. k가 남았다면 뒤에서부터 뺍니다.
    while k > 0:
        st.pop()
        k-=1

    answer = "".join(st)
    return answer

if __name__ == '__main__':
    number = "1924"
    k = 2
    print(solution(number, k))

 

CPP 코드는 다음과 같습니다. 여기서는 추후에 스택을 0부터 순회해야하기 때문에, 벡터를 스택처럼 사용하였습니다.

 

#include <string>
#include <vector>

#include <iostream>

using namespace std;

string solution(string number, int k) {
    // 1. 스택 생성
    vector<char> st;
    
    // 2. 앞자리가 가장 큰 수가 되게끔 스택에 데이터 저장
    for (const auto & elem : number) {
        while (!st.empty() && st.back() < elem && k > 0) {
            st.pop_back();
            k -= 1;
        }

        st.push_back(elem);
    }
    
    // 3. k가 남았다면, 스택 뒤에서 k개 빼줌
    while (k > 0) {
        st.pop_back();
        k -= 1;
    }
    
    string answer = "";
    
    for (const auto & elem : st) {
        answer += elem;
    }
    
    return answer;
}

int main() {
    string number = "1924";
    int k = 2;
    cout << solution(number, k) << endl;
    return 0;
}