프로그래머스 '큰 수 만들기' 문제풀이 - Henry's Algorithm

 

문제 설명

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

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

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

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

입출력 예

numberkreturn

1924	2	94
1231234	3	3234
4177252841	4	775841

 

 

 

 

문제푸는 방법:

첫번째 방법: 처음에 문자열을 slice해서 접근하는 방법으로 풀어보았다. 그런데 8,10번 케이스에서 자꾸 시간초과 에러가 발생했다.

두번째 방법(정답): 결국 구글링을 통해 스택을 이용해서 풀었다. 

1) 스택에 하나씩 집어넣는다.

2) 큰 녀석이 들어오면 그 동안 쌓인 스택에서 하나씩 비교한 후 작은 놈을 제거해준다.

3) 제거해줄때마다 count + 1 해준다.

4) count == k 가 된다면 남아있는 아직 넣지 않은 number에 대한 값들을 stack에 전부 넣어준다.

5) 그리고 stack에 있는 값들중 len(number)-k 만큼만 출력해준다.

6) 마지막에 "".join(stack[:len(num)-k])를 반환해준다.

그 이유는 12번 케이스같은 경우 입력값 number = "54321" / k = 4로 테스트해보면,

stack = ["5","4","3","2","1"] 이 들어있다.

그래서 1개만 출력을 해주어야 한다.

 

정답코드:

def solution(number, k):
    answer = ''
    num = list(number) 
    stack = [num[0]] 
    count = 0
    
    for i in range(1,len(num)):
        if count == k:
            stack = stack + num[i:]
            break
        
        stack.append(num[i])
        if stack[-1] > stack[-2]:
            while len(stack) != 1 and stack[-1] > stack[-2] and count < k:
                del stack[-2]
                count += 1
    return "".join(stack[:len(num)-k])

 

참조: 나도 첫번째 방법으로 하다가 구글링해서 풀었다.ㅠㅠ

kdgt-programmer.tistory.com/5?category=1121942

[프로그래머스] 큰 수 만들기 - 그리디 greedy | 스택 Stack (python) (2)

blog.naver.com/PostView.nhn?blogId=lhaayyy&logNo=221889005763

[프로그래머스/c++] 큰 수 만들기 (+12번 테스트케이스)