[프로그래머스] 큰 수 만들기(LV2 - Python)

프로그래머쓱

해당 글에서는 큰 수 만들기 문제를 Python을 이용해 풀이하고자 한다.

프로그래머스

 

🔷 문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

 

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

 

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한 조건 number는 2자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다.

 

제한 조건

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

 

🔷 문제 풀이

1️⃣ 첫 번째 풀이

처음에는 단순한 풀이를 생각했다.

일단 가장 큰 숫자를 만들기 위해선, return 되어야 하는 값의 앞자리에 올 수록 큰 수가 들어가야 한다는 것은 쉽게 알 수 있는 사실이다.

number의 길이를 N이라고 하면, return 하고자 하는 수의 길이는 N-k가 되어야 한다.

 

또한, return의 i번째 오는 수는 number의 0번째~(N-k+i)번째에 있는 수가 선택될 수 있다. 그리고 이전에 선택된 수 이후에 숫자만 고를 수 있다.

예를 들면 [number = "1924", k =2]인 경우에 return의 첫 번째 수는 "192"중에 선택되어야 하며, 두 번째 수는 "1924"중에 선택될 수 있다. 첫 번째 수는 "192" 중에 9가 선택 되고, 두 번째 수는 첫 번째에 선택된 9 이후에 있는 "24" 중에 큰 값인 4가 선택 되어야 한다.

 

위와 같이 풀이한 결과 다음과 같다.

def solution(number, k):
    answer = ''
    
    N = len(number)
    visit = [False] * N # 사용했는지 여부
    cur = -1
    for i in range(N - k, 0, -1):
        # print(i)
        num = -1
        idx = -1
        for j in range(cur+1, N-i+1):
            # print(f'cur: {cur}, number: {number[j]}')
            if int(number[j]) > num and visit[j] == False:
                num = int(number[j])
                idx = j
                cur = idx
                if num == 9:
                    break
        visit[idx] = True
        answer += str(num)
        
    return answer

이때, num이 9일 때 예외처리를 해주지 않으면 시간초과가 난다.

 

2️⃣ 두 번째 풀이

문제를 풀면서 계속 첫 번째 풀이 보다 효율적인 풀이가 있을 것이라고 생각이 들었다. 하지만 도무지 떠오르지 않았고, 구글링을 통해 더 효율적인 두 번째 방식을 알 수 있었다.

이 글을 쓰게 된 것도 두 번째 풀이 때문이다. 이해하는 과정이 조금 어려워서 글을 작성하여 더 오래 기억하고자 기록을 하기로 했다.

 

두 번째 풀이는 Stack을 이용한 풀이이다.

number의 수를 처음부터 순회하면서(편하게 그 숫자를 num이라 하자) Stack이 비어있을 때는 num을 그냥 추가한다.

Stack이 비어있지 않은 경우에는 top에 있는 숫자와 num을 비교하고, top이 num 보다 작은 경우 계속 pop을 하다가 answer가 비거나 num보다 더 크거나 같은 수가 나오면 num을 Stack에 추가한다.

만약 pop을 한 경우 k개의 수에서 하나를 제거한 것이므로 k-1을 해줘야 한다. k가 0이 되는 경우 더 이상 숫자를 뺄 수 없으므로, 남은 수를 모두 Stack에 추가한다.

 

말로 이해하긴 어려우므로 아래 필기를 통해 이해해보자.

 

[number = "1924", k = 2인 경우]

number의 순서대로(1, 9, 2, 4) 순회하면서 위와 설명한 것과 같이 진행해보자.

• num = "1"
  • 처음 stack은 비어있는 상태이므로 1을 넣어주자.
  • stack = [1]
• num = "9"
  • top에 있는 1보다 큰 값이므로 stack.pop을 진행하여 1을 제거한다.
  • pop을 진행했으므로 k에서 1을 뺀다 (k=1)
  • stack = []
  • stack이 비었으므로 9를 넣어주자.
  • stack = [9]
• num = "2"
  • top에 있는 9보다 작은 값이므로 stack에 2를 넣어주자.
  • stack = [9, 2]
• num = "4"
  • top에 있는 2보다 큰 값이므로 stack.pop을 진행하여 2를 제거한다.
  • pop을 진행했으므로 k에서 1을 뺀다(k=0)
  • stack = [9]
  • top에 있는 9보다 작으므로 4를 넣어주자.
  • stack = [9, 4]

number의 끝까지 순회가 완료 됐으므로, stack을 출력해주면 된다.

따라서 결과는 "94"가 된다.

 

[number = "918765", k = 2인 경우]

위 예제처럼 k가 0이 되는 예제도 있지만, k가 0이 되지 않는 예제도 있다.

해당 경우에는 위 과정과 동일하게 진행하면 stack에서 pop되는 수가 없으므로 stack은 98765가 남으며, k=1가 된다.

 

따라서 stack에 남은 수에서 남은 k만큼 제거해줘야 한다. 즉, 작은 수가 위치한 stack의 pop 부분부터 k개를 없애야 하므로 파이썬에서는 stack[:-k]를 반환하면 된다.

 

위를 풀이한 코드는 다음과 같다.

def solution(number, k):
    answer = [] # stack
    
    for num in number:
        if not answer: # answer가 비어있는 경우
            answer.append(num)
            continue
        
        while k>0 and answer[-1] < num: # 이후에 오는 숫자가 더 큰경우
            answer.pop() # 이전 숫자 제거
            k -= 1 # 하나 제거 했으므로 k-1
            if not answer:
                break
        answer.append(num)
        
    answer = answer[:-k] if k>0 else answer
    
    return "".join(answer)