[Python3]프로그래머스_큰 수 만들기

문제출처: https://programmers.co.kr/learn/courses/30/lessons/42883#

접근법

1. 처음에 (현재 인덱스) ~ (현재 인덱스 + k) 까지의 숫자들 중에서 가장 큰 숫자를 정답에 추가하고 가장 큰 숫자의 앞 숫자들은 제거한 숫자들로 계산한다.
   그리고 정답에 추가된 숫자 다음부터 반복하는 구조로 O(n) 시간 안에 해결이 될 줄 알았으나 단순하게 while문 또는 for문으로 구성할 경우 시간이 오래 걸리는 문제가 있었다.

• 실제로 10번 테스트 케이스에서만 시간초과로 계속 실패

2. 이는 아마 현재 숫자와 (현재인덱스+k)번째 숫자들을 모두 비교했을 때 자신과 같거나 낮은 경우에 인덱스별 비교 연산이 많이 들어가서 각 숫자는 한번씩 비교되는 것이 아니라 시간 복잡도 O(n)이 보장되지 않아서 그런것 같다.

• 0,1 로만 구성된 1,000,000자리 숫자들인 경우 극단적으로 시간 복잡도가 증가할 수 있다.

3. 하루정도 10번 테스트 케이스때문에 고생하다 스택을 활용해야 한다는 팁을 보고 코드를 작성 후 제일 효율적으로 보이는 코드를 참조하여 수정해보았다.
위의 접근법은 다음 숫자가 이전까지 나온 숫자들보다 클 시 횟수 k만큼은 제거할 수 있었다. 그리고 순차접근을 보장하고 스택구조를 활용하면 이전까지 나온 숫자들 중 마지막 숫자를 다음 숫자와 비교하여 제거할지 말지 쉽게 판단할 수 있었다.

코드

(오답코드 1)
# def solution(number, k):
#     answer = ''
#     s = []
#     for i in range( len(number) ):
#         if( i == len(number)-k ):
#             k -= 1
#             continue
#         j = i + 1
#         flag = True
#         while( j <= i+k and j < len(number) ):
#             if( number[j] > number[i] ):
#                 flag = False
#                 break
#             j += 1
#         if( flag ):
#             s.append(number[i])
#         else:
#             k -= 1
#     answer = ''.join(s)
#     return answer
(오답코드 2)
# def solution(number, k):
#     answer = ''
#     i = 0
#     while( i < len(number)-k ):
#         j = i+1
#         m,index = "" , 0
#         while( j <= i+k  ):
#             if( m < number[j] ):
#                 m = number[j]
#                 index = j-i
#             j += 1
#         answer += m
#         i += index + 1
#         k -= index
#     return answer

정답코드)

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