개발 학습 블로그입니다.

2 minute read

프로그래머스 연습 문제 중 42883번 ‘큰 수 만들기’

https://programmers.co.kr/learn/courses/30/lessons/42883

문제 설명

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

풀이

나의 풀이

처음엔 간단하게 모든 조합을 탐색해 최대의 값을 구했었는데 시간초과가 떴다. 단순 탐색이 아닌 방법이 필요했다.

문제에 적합한 그리디한 논리는 쉽게 떠올렸지만, 코드로 구현하는데 시간이 오래걸렷던 문제였다. 아이디어는 이렇다. 주어진 number의 총 갯수를 n, 제거할 수 있는 갯수가 k라면 우리가 얻을 수 있는 문자열 return은 n - k개가 된다.

  1. 입력으로 주어진 number의 순서는 바꿀수 없으므로, 최대의 return 값을 얻으려면 return의 첫번째 자리의 수는 number[0:-(n - k - 1)] (0번째 인덱스부터 n-k-1번째 인덱스까지 존재하는 모든 수)중 최대의 값을 가지면 된다. 이때의 최댓값을 max_num에 저장하고, 이때의 인덱스 또한 m에 저장해 두번째 자리 수 탐색에 사용한다.

  2. retrun의 두번째 자리수는 number[m+1:-(n - k- 1) + 1] (첫번째 자리 숫자인 m이후의 인덱스인 m+1 번째 인덱스 부터 -(n - k- 1) + 1번째 인덱스 까지 존재하는 모든 수)중 최대의 값을 가지면된다. 이때의 최댓값을 다시 max_num에 저장하고, 이때의 인덱스 또한 m에 저장해 세번째 자리 수 탐색에 사용한다.

  3. 1번 2번 과정을 l < 0 동안 진행한다.

  4. 각 자리수들과 마지막 자리수는 number[m:]에 남아있는 수 중 최댓값을 합해주면 return이 최대값이 된다.

def solution(number, k):
     # 모든 number를 int로 저장
    int_number = list(map(int, list(number)))
    n = len(number)
    m = 0
    l = -(n - k - 1)
    tmp = ''
    while l < 0:
        max_num, idx = 0, m
        for num in int_number[m:l]:
            # 만야 max_num이 9라면 더이상의 탐색은 무의미하다.
            if max_num == 9:
                break
            # 최댓값이 갱신될때마다 max_num, m도 같이 갱신
            if num > max_num:
                max_num = num
                m = idx + 1
            idx += 1
        l += 1
        tmp += str(max_num)
    # 탐색이 모두 끝나고 마지막 자리는 number[m:]중 최댓값을 더해주면 된다.
    return tmp + max(number[m:])

다른 사람의 풀이

내 풀이로 통과는 했으나 다른 사람의 풀이에 더 깔끔하고 명확한 코드가 있었다.

  1. stack에 number의 첫번쨰 성분을 넣는다.
  2. 나머지 number[1:]성분을 순차적으로 스캔한다.
  3. 제거할 수 있는 횟수가 남아있고, 스택의 마지막 성분보다 num이 더 작다면 k의 횟수에 1을 빼고, 해당 성분을 스택에서 지운다.
  4. 제거할 수 있는 횟수가 없거나, 스택의 마지막 성분이 num보다 클때까지 3을 반복한다.
  5. 모든 num에 대해 2, 3, 4를 마친후 stack은 최댓값이 된다.
  6. 만약 k가 0이 아니라면 더이상 제거할 수 없어 stack에 추가된 성분이므로 stack[:-k] (k개 만큼 잘라냄)을 통해 stack을 수정해준다.
def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        print(stack)
        while len(stack) > 0 and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)
    if k != 0:
        stack = stack[:-k]
    print(f'stack: {stack}')
    return ''.join(stack)

solution("4177252841", 4)

['4']
['4', '1']
['7']
['7', '7']
['7', '7', '2']
['7', '7', '5']
['7', '7', '5', '2']
['7', '7', '5', '8']
['7', '7', '5', '8', '4']
stack: ['7', '7', '5', '8', '4', '1']

Leave a comment

You may also enjoy