프로그래머스 그리디 문제입니다.

문제

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

주어진 숫자 문자열을 조합하여 가장 큰 수를 만드는 문제입니다.

[나의 풀이1]

(시간 초과)

def solution(number, k):
    from itertools import combinations
    
    number = list(number)
    indexes = [idx for idx in range(len(number))]
    value = 0

    for case in combinations(indexes,k):
        case = list(case)
        origin = list(number)
        cnt = 0
        for i in case:
            del origin[int(i-cnt)]
            cnt += 1
        now = int("".join(origin))
        if now > value:
            value = now
    #print(value)
    return str(value)

최초 구현 시에 숫자들을 조합할 수 있는 모든 경우의 수를 구하여 비교하며 가장 큰 수를 찾는 방식으로 구현하였습니다. 하지만 combinations함수,2중 for문으로 인해 시간초과되는 케이스가 발생하였습니다.🐕🐕🐕

그리하여 문자열을 특정 구간씩 슬라이싱하고 그 중 최고값을 갖는 수를 한개씩 더하는 방식으로 풀고자 하였습니다.

[나의 풀이2]
(시간 초과)

def solution(number, k):
    import numpy as np
    cnt = len(number)-k
    answer = ''
    
    if cnt == 1:
        return max(list(number))
    
    tmp = []
    # tmp = [1,9]
    tmp = number[:1-(cnt)]
    while cnt>0:

        tmp = list(tmp)
        max_idx = np.argmax(tmp)
        
        number = number[max_idx+1:]
        answer += tmp[max_idx]
        
        cnt -= 1

        if cnt == 1:
            answer += max(number)
            cnt -= 1

        tmp = number[:-(cnt-1)]

    return answer

위의 코드는 cnt(최종 문자열의 크기)를 체크하며 후에 더 제거해야하는 숫자들의 갯수를 감안하여 그 앞에 있는 수들 중에서 최고값을 answer에 순차적으로 더하는 방식이었습니다. 하지만 이 방법 또한 여러번의 슬라이싱을 통해 답을 도출하다 보니 또 다시 일부 케이스에서 시간초과가 발생하였습니다. 그리하여
다른 풀이를 참고하게 되었습니다.🐢🐢🐢

[다른 사람의 풀이1]

def solution(number, k):
    answer = [] # Stack
    
    for num in number:
        if not answer:
            answer.append(num)
            continue
        if k > 0:
            while answer[-1] < num:
                answer.pop()
                k -= 1
                if not answer or k <= 0:
                    break
        answer.append(num)
        
    answer = answer[:-k] if k > 0 else answer
    return ''.join(answer)

stack을 이용한 풀이입니다. number의 요소를 돌며 answer안에 아무 숫자도 없을 시에는 일단 append합니다. 그리고 k>0(제거해야할 횟수가 0이 아닐때)
최후방에 있는 숫자를 확인하며 더 작은 값일 시 pop()하고 이때마다 k값을 1개씩 내리고 더 큰값을 append하는 구조입니다. 이 과정을 answer가 비어있거나 제거할 횟수가 0일때(k=0)까지 반복하여 answer를 완성하는 구조입니다.
만약 '4321'과 같이 내림차순으로 되어있는 문자열이라면 pop()하는 과정은 없어 k가 양수이고 answer의 k번째인덱스는 제외하고 출력하는 방식입니다.🐻🐻🐻

비슷한 방식의 풀이로 다른 표현은

[다른 사람의 풀이2]

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

solution(['4123'],2)

입력값에 따라 k가 양수일 수 있고 0이 될 수 있기 때문에 return 값에

''.join(answer[:len(answer) - k])

k값이 포함된 수식을 활용한 슬라이싱 방식이었습니다.

감사합니다.