[Python] 프로그래머스, 큰 수 만들기 Lv.2 (feat.greedy, stack, combinations, 시간 초과, 파이썬)

반짝반짝 알고리즘, 인프준

 

 

 

 

 

 

 

 

 

 

큰 수 만들기

문제 링크

프로그래머스

 

 

문제 설명

어떤 숫자에서 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	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

 

 

 

 

 

---

 

 

 

 

 

 

해결 과정

 

만들어질 수 있는 모든 조합을 확인하기 위해서 combinations 함수를 사용했습니다.

 

[Python] 누적합 / 순열 / 조합 (feat.itertools module)

 

 

"number의 길이"에서 "제거할 수의 개수 k"를 뺀 값으로 조합을 만들고 join 함수를 통해 문자열로 만들어 준 뒤 max 함수를 통해 최댓값을 출력하였습니다.

 

 

 

첫 번째 제출 코드

from itertools import combinations
def solution(number, k):
    return max(list([ ''.join(i) for i in combinations(number, len(number)-k)]))

 

 

 

위 코드의 경우 논리에 문제가 없어 자릿수가 적을 때는 해결 가능하지만 자릿수가 커짐에 따라 조합이 많아지면서 시간 초과가 발생하게 됩니다. 그렇기 때문에 좀 더 연산을 줄일 필요가 있습니다.

 

 

 

최종 제출 코드

def solution(number, k):
    # 스택 선언
    stack = []
    
    # number의 길이만큼 for loop
    for num in number:
        # 1. 제거할 수 k가 남았고
        # 2. 스택에 값이 있고
        # 3. 스택의 마지막 값이 num보다 작다면
        # 제거 후 제거할 수 k를 1씩 감소 
        while k > 0 and stack and stack[-1] < num:
            stack.pop()
            k -= 1
        # 스택에 num 추가
        stack.append(num)
    
    # k가 남아있는 경우 - 테스트 케이스 number: "93939", k: 2, 출력: 999, 실제정답: 99
    if k != 0:
        stack = stack[:-k]
    
    # 배열을 문자열로 바꿔주고 반환
    return ''.join(stack)

 

 

 

1. 스택을 선언해 주고 number의 길이만큼 for loop을 돌려줍니다.

 

2. 아래의 조건을 만족할 경우 while loop을 반복하며 stack의 마지막 값을 제거하고 k를 1씩 감소시켜 줍니다.

• 제거할 수 k값이 남아있다.
• 스택이 비어있지 않다.
• 스택의 마지막 값보다 현재 num이 작다.

 

3. k가 남아있다면 ( 0이 아니면 ) k개를 삭제해 주고 join 함수를 사용해 문자열로 반환해 줍니다.

 

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

Pseudo Code

 

입력 받은 numbers를 리스트로 저장

result = number의 첫번째 요소를 꺼내어 result에 저장

for n in number

    if 이전 요소(result의 마지막 요소) 가 현재 요소보다 작다면

         while 이전 요소가 남아있음 and 이전 요소(result의 마지막 요소)< 현재 요소 and 아직 k개의 수가 제거 안됨

              결과의 마지막 요소 제거

              k -= 1

    elif 이미 k개의 수가 제거됨 또는 이전 요소(result의 마지막 요소)가 현재 요소보다 큼

          결과에 현재 요소 추가



if 아직 k개의 수가 제거 안된 경우 

      result의 뒤 부터 제거

 

 

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

 

 

 

출처: 프로그래머스 코딩 테스트 연습,https://school.programmers.co.kr/learn/challenges