[프로그래머스] Level2_큰 수 만들기(Greedy)

📌문제 유형

Greedy

 

📌문제

프로그래머스

 

📌문제 풀이

1차 시도 (33.3 - 시간초과)

from itertools import combinations

def solution(number, k):
    answer = ''
    num = []
    new_nums = []
    
    # 값 하나씩 문자로 넣기
    for i in range(len(number)):
        num.append(number[i])
        
    # n개의 숫자만 선택
    n = len(number) - k
    nums = tuple(combinations(num, n))
    
    for i in range(len(nums)):
        new_nums.append(int(''.join(nums[i])))
        
    return str(max(new_nums))

2차 시도(첫 번째 시도 간단 ver)

from itertools import combinations

def solution(number, k):
    answer = ''
    n = len(number) - k
    number = list(number)
    
    nums = sorted(list(map(''.join,combinations(number, n))), reverse = True)

    return nums[0]

3차 시도(예시만 통과)

def solution(number, k):
    answer = ''
    n = len(number)
    len_n = len(number) - k
    num = sorted(list(map(int,set(list(number)))), reverse = True)
    
    # 전체 개수 중 큰 값 1/2개만 남겨두기
    num = [num[i] for i in range(len(num)//2)]
    # 원래 숫자들
    number = list(map(int,number))
    
    i = 0
    for _ in range(n):
        if number[i] not in num:
            if len(number) > len_n:
                number.pop(i)
            else:
                return ''.join(list(map(str,number)))
        else:
            i += 1
            
    return ''.join(list(map(str,number)))

4차 시도(다른 사람의 풀이)

 - 값은 새로운 리스트에 하나씩 넣기

 - 새로운 리스트에 있는 값과 넣을 값을 비교(앞의 값만 비교)

프로그래머스

def solution(number, k):
    answer = []
    return not answer

    for i in number:
        # answer에 값이 없으면, 하나만 넣기
        if not answer:
            answer.append(i)
            continue
            
        # answer 마지막 값이 현재 값(i)보다 작은 경우와 k 고려
        while answer[-1] < i and k > 0:
            answer.pop()
            k -= 1
            # answer가 없거나 k가 조건에서 어긋날 때 멈춤
            if not answer or k <= 0:
                break
        answer.append(i)
        
        if len(answer) == len(number) - k:
            break
            
    return ''.join(answer)

 

📌다른 사람들의 풀이

1) 조금 더 간단한 코드

def solution(number, k):
    stack = [number[0]]
    
    for num in number[1:]:
        while len(stack) > 0 and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)
        
    # 제거 횟수를 다 사용하지 않았을 때, 횟수만큰 리스트 뒷부분 자르기
    if k != 0:
        stack = stack[:-k]
        
    return ''.join(stack)

 

📌리뷰

 - 새로운 리스트 만들고 하나씩 넣어서, 다음 수와 비교하기

 - 가장 정석적인 방법이 제일 효과적일 수도?!