[Programmers] 큰 수 만들기

 

문제 

 

어떤 숫자에서 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"

 

 

나의 코드 및 접근 방식  

def solution(number, k):
    p = len(number) - k
    array = []
    print(p)
    number = list(map(int,number))
    print(number)
    while True:
        if number[0] > number[1]:
            number.pop(1)
        elif number[0] < number[1]:
            number.pop(0)
        elif number[0] == number[1]:
            number[0] = number[number.count(number[0])]
        if len(number) == p:
            break
    
    return ''.join(map(str, number))

분석 > 이 문제를 처음 봤을 때 생각보다 간단한 문제인 것 같은데, 잘 안풀려서 당황했었다. 나의 경우 number 배열의 길이가 p가 될 때까지 배열의 첫번째 원소와 두번째 원소를 비교하면서 적은 수를 pop하는 방식으로 접근했다. 하지만 이 방법으로는 비교하는 원소들이 같은 수일 때를 해결하지 못했다. 그래서 테스트케이스 3번의 경우 원하는 답이 나오지 못하고 코드가 꼬이고 말았다. 

 

 

해설 코드 

def solution(number, k):
    answer = []
    for num in number:
        # answer에 값이 존재하며, k는 0보다 크고, answer의 최근 값이 현재의 num보다 작으면
        while answer and k > 0 and answer[-1] < num:
            # answer의 최근 값을 제거하고 k도 -1 해준다
            answer.pop()
            k -= 1
        # 현재의 num값은 무조건적으로 answer에 넣어준다
        answer.append(num)
    
    # answer는 number의 길이 - k만큼 슬라이싱 해준다.
    # -> 슬라이싱은 index 바깥으로 나가도 괜찮음! 
    # 일반적으로 k는 0일텐데 ex) k = 3 number = 1000000 이런 경우엔 k는 처음 인풋받은 그대로 유지됨
    # 이럴 때 답은 뒷 숫자를 k개만큼 없애준 1000 이므로 슬라이싱을 len(number) - k로 해주는 것
    answer = ''.join(answer[:len(number)-k])
    
    return answer

분석 > 우선 빈 배열의 answer 스택을 만든 후에 answer 값이 존재하며 k는 0보다 크고 answer의 가장 최근 값이 현재 num보다 작을 때 answer의 가장 최근 값을 pop한 후 최종 pop한 수를 나타내는 k에서 1을 빼가며 반복문을 돌린다. 그리고 num값은 계속 append하여 answer[-1]값과 계속 비교한다. 최종 출력값은 number 값이 1000000 이고 k = 3 인 경우 1000이라는 값을 제대로 출력하기 위해 len(number) - k 로 슬라이싱 해주어 출력한다.