Programmers | 큰 수 만들기 - Python

1. 개념 정리

1.1 탐욕법 (Greedy Algorithm)

현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘. 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있으면 매우 효과적이고 직관적인 알고리즘이지만, 대부분의 문제에 대해서는 "최적의 해"를 찾을 수 없는 가능성이 크기 때문에 주의해서 사용해야 하는 알고리즘입니다. 매 순간의 선택은 그 순간에 대해서는 최적이었을지라도 그것이 결론적으로 최적이 아닐 수 있기 때문입니다. 그렇기 때문에 그리디 알고리즘을 이용해 문제를 해법을 찾을 경우, 그 해법이 정당한지에 대해서 반드시 확인해 보아야 합니다.

대표적으로 거스름돈 문제가 있으며 다익스트라 알고리즘 또한 그리디 알고리즘이라고 할 수 있습니다.

2. 문제 설명

2.1 큰 수 만들기

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

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

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

2.2 제한 조건

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

2.3 입출력 예시

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

3. 풀이 과정

문자열로 주어진 숫자에 대해서 k개의 수를 제거하여 가장 큰 수가 되도록 만드는 문제입니다.

접근 방식만 잘 생각하면 10줄 내외로 풀이 할 수 있는 비교적 간단한 문제였지만, 알고리즘 문제 풀이를 시작한 지 얼마 되지 않아 많이 헤맸던 문제이기도 합니다.

3.1 조합과 정렬 : 실패😂

시간 초과가 났던 풀이 방식입니다. 실제로도 제한 조건이 100만 자리 이하의 자연수이기 때문에 시간 초과가 날 것을 예상하긴 했지만 가장 단순한 접근이라서 풀어보았습니다.

문제의 핵심은 k개의 수를 제거한 후, 가장 큰 수를 구하는 것이기 때문에 k개를 제외한 나머지 수를 순서와 상관없이 뽑는 모든 경우의 수에서 최댓값을 구하면 된다고 생각하여 조합을 활용 후 정렬하여 결괏값을 구할 수 있었습니다.

• 전체 코드 (python)

from itertools import combinations

def solution(number, k):
    answer = list(combinations(list(number), len(number)-k))
    return ''.join(sorted(answer, reverse = True)[0])

• 실행 결과
  

3.2 i번째 i+1번째 비교 : 실패😂

단순하게 접근해서 앞에서부터 i번째와 i+1번째 수를 비교해서 number[i] < number[i+1] 일 경우 number[i]를 총 k번 삭제하는 방법을 생각해 보았습니다. (number[i] == number[i+1] 일 경우에는 i++)

하지만, 이 경우에는 입출력 예시 1924와 1231234의 경우는 정답을 찾을 수 있지만 4177252841과 같은 경우는 결과가 772841이 되어서 정답을 찾을 수 없었습니다. (대충 테스트해 본 것이라 그 외에도 문제가 많긴 합니다;;)

• 전체 코드 (python)

def solution(number, k):
    number = list(number)
    i = 0
    while k > 0:
        start = number[i] 
        end = number[i+1]
        if(start != end):
            if(start < end):
                del number[i]
                k -= 1
            else:
                del number[i+1]
                k -= 1
        else:
            i += 1
    return ''.join(number)

• 실행 결과
  

3.3 작은 수 삭제 : 실패😂

앞선 접근 실패 후, 여러 고민을 해봤지만 다른 접근 방식이 떠오르지 않아서 안 될 것을 알면서도 한 번 시도해본 방식입니다... 숫자는 0~9까지로 이루어져 있으니까 큰 수를 만들려면 작은 수부터 제거해보자는 생각으로 number에 포함된 0~9까지 수의 개수를 count 한 후 0부터 시작해서 k개만큼을 제거해 보았습니다.

결론적으로 이 방식도 전체에서 작은 수를 제거하는 것이 아닌 앞에서부터 작은 수를 제거해서 큰 수를 만들어야 하는데 그렇지 못해서 실패한 방식입니다.

• 전체 코드 (python)

def solution(number, k):
    digit_count = dict()
    for i in range(10):  # 0부터 9까지
        count = number.count(str(i))
        if(count != 0):
            digit_count[i] = count
            
    for key in digit_count.keys():
        if(k <= 0): 
            break
        
        count = digit_count[key]
        if(count <= k):
            number = number.replace(str(key), '')
            k -= count
        else:
            number = number.replace(str(key), '', k)
            break
    return number

• 실행 결과
  

3.4 Stack(LIFO) 활용 : 성공😋

마지막 시도로 살짝 구글링을 통해 힌트를 얻고 풀이를 진행하였습니다. 앞선 시도에서는 제거에만 초점을 두고 문제를 풀이하였는데 Stack을 활용해서 문제를 풀 수 있다는 것을 알게 되니까 push와 pop 두 가지를 사용해서 풀이하는 방식을 생각해 보았습니다.

• 핵심은 스택의 마지막 값이 push 할 값보다 작다면 크거나 같은 값이 나올 때까지 값들에 대해서 pop을 하는 것입니다.
• 이렇게 풀이하면 O(n)의 시간 복잡도로 문제를 해결할 수 있습니다.

3.4.1 알고리즘

1. 스택 생성 => 파이썬에서는 리스트 활용 가능
2. number를 순회 => for num in number:
   1. 다음 조건문을 모두 만족할 경우 명령문을 반복
   2. 조건문
      1. k > 0
      2. 스택이 비어있지 않음
      3. 스택 마지막 값 < num
      2. 명령문
         1. 스택을 pop
         2. k--
   3. 스택에 num을 push
3. k > 0 이상이면 스택에서 k개 삭제 후 join해서 결과 값 반환

3.4.2 풀이 예시

앞자리에 큰 숫자가 오는 것이 전체 수를 크게 만들 수 있습니다.

• number = "4177252841", k=4일 경우,

  • (k=4) []
  • (k=4) [4]
  • (k=4) [4, 1]
  • (k=3) [4]
  • (k=2) []
  • (k=2) [7]
  • (k=2) [7, 7]
  • (k=2) [7, 7, 2]
  • (k=1) [7, 7]
  • (k=1) [7, 7, 5]
  • (k=1) [7, 7, 5, 2]
  • (k=0) [7, 7, 5]
  • (k=0) [7, 7, 5, 8]
  • (k=0) [7, 7, 5, 8, 4]
  • (k=0) [7, 7, 5, 8, 4, 1]
  • retrun "775841"

• number = "999", k=2일 경우,

  • (k=2) []
  • (k=2) [9]
  • (k=2) [9, 9]
  • (k=2) [9, 9, 9]
  • return "9"

3.4.3 1차 코드

• 전체 코드 (python)

def solution(number, k):
    answer = [] # Stack
    
    for num in number:
        if not answer:
            answer.append(num)
            continue
        if k > 0:
            while answer[-1] < num:
                answer.pop()
                k -= 1
                if not answer or k <= 0:
                    break
        answer.append(num)
        
    answer = answer[:-k] if k > 0 else answer
    return ''.join(answer)

• 실행 결과
  

3.4.4 2차 코드

1차 코드에서 중복되는 부분이나 불필요한 부분을 줄이고 최적화된 코드로 작성해보았습니다.

• 전체 코드 (python)

def solution(number, k):
    answer = [] # Stack
    
    for num in number:
        while k > 0 and answer and answer[-1] < num:
            answer.pop()
            k -= 1
        answer.append(num)
        
    return ''.join(answer[:len(answer) - k])

• 실행 결과
  

4. 핵심 정리

4.1 🔥 최종 풀이 🔥

def solution(number, k):
    answer = [] # Stack
    
    for num in number:
        while k > 0 and answer and answer[-1] < num:
            answer.pop()
            k -= 1
        answer.append(num)
        
    return ''.join(answer[:len(answer) - k])

4.2 핵심 포인트

• Stack을 활용하기
• 예외 케이스까지 고려하기
• 중복된 코드 줄이고 최적화 된 코드 작성하기

4.3 주요 라이브러리

• list(append, pop)
• String join

4.4 참고 링크

• 프로그래머스 문제 풀이 큰 수 만들기
• [프로그래머스] 큰 수 만들기 / 파이썬
• 파이썬 고득점키트 문제풀이(4) 탐욕법_큰수만들기
• [프로그래머스] 큰 수 만들기 (python)