[Programmers/Python] 큰 수 만들기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42883?language=python3 

 

풀이

 

예) number = '1231234', k = 3, answer = '3234'

1. 결과는 number의 길이 7에서 3을 뺀 4자리가 된다.

2. 처음엔 number의 k+1 전까지의 범위를 탐색하여 최댓값을 찾아, answer에 추가하고 index는 저장한다. (최댓값이 여러 개라면 앞에 있는 index의 최댓값으로 선정한다. 나중에 탐색할 문자열이 많을 수록 최댓값이 커지기 때문이다. )

3. 2번의 과정을 n-k 번 반복한다. 대신 문자열 범위는 처음부터가 아닌 최댓값의 index +1 부터 k+1+t 까지 탐색한다.  

 

1)

def solution(number, k):
    n = len(number)
    i = 0   
   
    answer = ''
    for t in range(n-k):    # t=0,1,...,n-k-1 (n-k번)
        max_idx = -1        # 최댓값 인덱스 초기화
        max_val = -1        # 최댓값 초기화
     
        for idx in range(i,k+1+t):  
            if(int(number[idx]) > max_val):
                max_idx = idx
                max_val = int(number[idx])

        i = max_idx+1
        answer+=str(max_val)
   
    return answer

풀이 1과 2의 정확성

시간복잡도가 크다.

이를 개선하는 방법은.. 

숫자 9는 탐색하지 않는 것이다. 어차피 9가 가장 큰 값이기 때문이다. 

 

2)

def solution(number, k):
    n = len(number)
    i = 0   
   
    answer = ''
    for t in range(n-k):    # t=0,1,...,n-k-1 (n-k번)
        max_idx = -1        # 최댓값 인덱스 초기화
        max_val = -1        # 최댓값 초기화
     
        for idx in range(i,k+1+t): 
            if(number[idx]=='9'):
                max_idx = idx
                max_val = int(number[idx])
                break
                
            if(int(number[idx]) > max_val):
                max_idx = idx
                max_val = int(number[idx])

        i = max_idx+1
        answer+=str(max_val)
   
    return answer

 

다른 사람의 stack을 이용한 풀이) 

중간과정을 출력한 그림을 보면 이해하기 쉽다.

핵심은 "앞자리를 최고 큰 수로 만들기 전략"이다.

먼저 큰 수를 만드는 문자들을 모으는 배열 st 를 생성한다. 

number를 다음과 같이 순회한다.

아래의 조건을 만족시키면 다음을 순회한다.

1. 조건

- st 에 원소가 있어야한다. 

- k가 0보다 커야 한다.

- st의 마지막 원소가 순회하는 수 number[i]보다 작아야한다.

 

2. st의 가장 맨 뒤의 원소를 제거한다. pop()

3. k에서 1을 뺀다

 조건에 해당되지 않는다면 순회하는 수를 st의 맨 뒤에 넣는다. append()

https://eda-ai-lab.tistory.com/465?category=766271 

def solution(number, k):
    # stack에 입력값을 순서대로 삽입 
    stack = [number[0]]
    for num in number[1:]:
        # 들어오는 값이 stack 값보다 크면, 기존의 값을 제거하고 새로운 값으로 바꿈 
        # 참고 : len(stack) > 0 == stack
        while len(stack) > 0 and stack[-1] < num and k > 0:
            # 값을 한개 빼서 k는 1이 제거 
            k -= 1
            # 내부의 값을 제거 
            stack.pop()
        # 새로운 값을 삽입 
        stack.append(num)
    # 만일 충분히 제거하지 못했으면 남은 부분은 단순하게 삭제
    # 이렇게 해도 되는 이유는 이미 큰 수부터 앞에서 채워넣었기 때문 
    if k != 0:
        stack = stack[:-k]
    return ''.join(stack)

이 풀이의 시간복잡도가 낮은 이유는 문자열을 한 번만 탐색하기 때문이다. O(n)

나의 풀이는 자리수가 많아질수록 탐색해야하는 문자열의 범위가 겹치기 때문에 시간이 오래 걸리는 것 같다. O(n2)