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

알고리즘 문제 푸는 나...

 

문제 풀이 정리

 

문제 설명

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

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

이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다.

number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를

문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

제한 조건

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

입출력 예

number / k / return

"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

코드

def solution(number, k):
    answer = ''
    
    num_stack = []
    for index in range(len(number)):
        num = number[index]
        if len(num_stack) == 0:
            num_stack.append(num)
        else:
            if k > 0:
                while len(num_stack) > 0 and num_stack[-1] < num:
                    num_stack.pop()
                    k -= 1
                    if k == 0:
                        break
                if len(number) - k == len(num_stack):
                    continue
                else:
                    num_stack.append(num)
            else:
                num_stack.append(num)
                continue
                
    answer = ''.join(num_stack)
    return answer

 

문제 넋두리

오래도 걸린다 증맬

 

첫번째 접근

문제 설명을 보고 일반화를 해봤다.

n개중 k개를 제거해 뭘 만들어라~ => 조합의 문제인가? permutation? combination?

조아쓰 문제 줠라 쉽구만 딱대 알고리즘 햇반뚝딱

하고 풀었다가 응 시간초과~^^

 

두번째 접근

하긴;;; 자릿수가 커지면 permutation 백날 돌려도 경우의수가 너무 많아져서 안나올게 분명했다

my mistake...

그럼 어떤 규칙이 있겠지?

9~0까지 숫자를 반복하는데,

숫자가 첫번째로 등장하는 n번째 index에서 해당 숫자보다 작은 값들을 지워나가면 되지 않을까?

예를 들어 "4177252841" 의 경우

9 => 없고

8 => 4177252 841 => 8보다 작은 숫자가 지워야되는데 k=4 보다 많기 때문에 패스

7 => 41 77252841 => 7보다 작은 숫자 41을 지운다 / k=2로 줄어든다

6 => 없고

5 => 772 52841 => 5보다 작은 숫자 2 제거 / k = 1로 줄어든다

4 => 77528 41 => 4보다 작은 숫자 2 제거 / k=0으로 반복 종료

결과는 775841로 정답과 완벽일치 ^오^

바로 무지성 채점 => 응^^틀림

 

반례를 생각해봐도 틀린 답이라는게 나온다

"66666" k=3 이라고 하면 숫자 6에서 아무것도 제거 하지 못하고 종료...

 

세번째 접근

프로그래머스 질문하기 탭에서 고수성님들 풀이를 들어보자

스..스택...스..스고이...

스택을 이용해라...그저 빛...

스택을 이용할때 이문제의 핵심은 뒤에 오는 숫자는 일단 넣는다

단, 이전 숫자가 넣으려는 숫자보다 클때 이전숫자를 제거하고 넣는다

두번째, 제거하려는 숫자만큼의 길이를 만족한다면, 삽입그만~

 

두번째 조건을 추가한 이유는 다음과 같다

"66655" k=3일 경우

첫번째의 경우 k는 줄어들지 않고, 무지성 삽입만 해댄다.

 

무튼 이렇게 한문제 또 풀이 끝~ 아유 재밌땅