[프로그래머스-42883] 큰 수 만들기 문제풀이: 파이썬, 자바스크립트

그리디 알고리즘의 두 번째 문제이다. 프로그래머스 레벨 2 문제였고, 단순 구현을 넘어 최대한 효율적으로 짜는 것이 관건이었다.

 

문제

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.


제한 조건
number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.

 

해결 아이디어

 

위 문제는 주어진 숫자 문자열에서 k개의 숫자를 제거해 가장 큰 수를 만드는 문제이다. 이때 앞자리부터 가장 큰 숫자를 선택하는 그리디 전략을 사용하여 최적의 해를 구한다. 

 내가 스스로 생각한 방법은 다음과 같았다.

 

1. 현재 자리에서 선택할 수 있는 범위를 정한다.

• 이전 단계에서 선택한 숫자 인덱스의 다음 자리부터, 남은 숫자를 다 채우기 위해 필요한 최소 숫자만큼의 범위까지만 탐색한다.

2. 그 범위에서 가장 큰 숫자를 선택하고, answer에 추가한다.

3. 선택한 숫자의 인덱스 다음 자리부터 다시 1~2번을 반복한다.

4. 모든 숫자를 선택할 때까지 이 과정을 반복하면 최종적으로 가장 큰 수가 만들어진다.

 

그래서 나는 아래와 같이 코드를 작성하였다.

def solution(number, k):
    answer = ''
    max_index = -1
    cnt = len(number)-k
    while cnt > 0:
        max = -1
        for i in range (max_index+1,len(number) - cnt + 1):
            if max < int(number[i]):
                max = int(number[i])
                max_index = i
        cnt -= 1
        answer += number[max_index]

    return answer

 

 

 

 

max_index랑 max의 초기값을 0으로 두었더니 오류가 생겨 -1로 두었다. (number에 0이 들어갈 수 있기에 아예 들어가지 않는 -1로 하는게 좋은 것 같다.)

또한 for문에서 i의 범위가 조금 헷갈렸는데, max_index의 다음원소부터, 전체 길이에서 골라야되는 남은 원소가 모두 끝에 몰려있는 경우의 가장 인덱스 위치까지로 잡았다. 

 그렇게 선택이 모두 완료될 때까지 매 순간 선택된 최댓값을 answer에 이어붙여 정답을 반환하도록 했다.

 

그러나, 이 문제는 테스트 케이스 2가지를 통과하지 못하였다.

시간복잡도가 최악인 경우 O(n^2)이기에, 해당 케이스에서는 시간 초과로 실패하였다.

 

분기한정법?

 

테스트 케이스 중 이런 경우가 있을 수 있다.

1999999999.....

위에 내가 적은 로직은, i의 범위안에서 계속 순회하면서 최댓값을 찾는데, 사실 모든 자리의 숫자는 9보다 클 수는 없기 때문에, 9가 나오는 순간 최댓값은 9로 확정이된다. 즉, 9가 나오면 반복문은 종료된다는 것이다.

따라서 코드를 아래와 같이 수정하였다.

 

해결코드 <Python>

def solution(number, k):
    answer = ''
    max_index = -1
    cnt = len(number)-k
    while cnt > 0:
        max = -1
        for i in range (max_index+1,len(number) - cnt + 1):
            if max < int(number[i]):
                max = int(number[i])
                max_index = i
                #9가 나오면 반복문 종료
                if max == 9:
                    break
                    
        cnt -= 1
        answer += number[max_index]

    return answer

 

위와 같이 수정하였더니 모든 테스트 케이스를 통과하였다. 

그러나 여전히 시간복잡도는 O(N^2)이다.

 

따라서 다른 분들의 코드를 보았는데, 스택을 사용하여 시간복잡도를 O(N)으로 획기적으로 줄일 수 있었다.

스택을 이용한 풀이?

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]: #두 번째 숫자부터 순회
        while len(stack) > 0 and stack[-1] < num and k > 0:
            k -= 1 #pop으로 없앤 애는 어차피 작은 숫자라 쓰일 일 없음: 제거하는 숫자.
            stack.pop() #stack의 top보다 num이 더 크면 stack.pop()으로 현재 top 없앰
        stack.append(num) # 더 크다면 stack에 넣음.
    if k != 0:
        stack = stack[:-k] # 제거 횟수를 다 사용하지 않았다면 뒷 부분 자르기
    return ''.join(stack)

 

스택은 LIFO(Last-In-First-Out)구조로, 항상 가장 마지막 숫자와 현재 숫자를 비교하기에 적합하다.

현재 숫자가 더 크면, 앞에 있던 숫자를 제거(pop)하면 돼서, 큰 수를 남기고 불필요한 숫자를 제거해 큰 수를 만드는 데 최적화된 자료구조다.

stack에서의 push/pop은 시간복잡도가 O(N)으로 효율적이다.

 

 

• 숫자를 보며 앞의 숫자가 작으면 제거
• 제거할 기회를 다 쓰면, 그냥 스택에 쌓음
• 마지막에 남은 k만큼 뒤에서 제거
• 한 번의 순회로 끝나므로 O(N)

 

 

예를들어, number = "54321"이고 k=2이면 while에서 pop을 하지 못하고 스택 뒤에서 k개를 제거하는 것이다.

['5,'4','3','2','1'] -> ['5','4','3']

 

해결 코드 <JavaScript>

function solution(number, k) {
    let answer = '';
    const stack = [];
    
    for (let i = 0; i < number.length; i++) {
        const num = number[i];

        while (stack.length > 0 && stack[stack.length - 1] < num && k > 0) {
            stack.pop();
            k--;
        }
        stack.push(num);
    }

    if (k > 0) {
        stack.splice(stack.length - k, k); //배열에서 원하는 인덱스부터 k개를 제거하는 메서드
    }

    answer = stack.join('');
    return answer;
}

해당 코드를 자바스크립트로 바꾸면 다음과 같다.

python에서는 append()를 사용하지만, JS, Java,C++ 등 다른 언어는 push()를 사용한다.