[프로그래머스/Python] 알고리즘고득점Kit-탐욕법(Greedy)-큰수만들기

📌 문제 링크

https://school.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의 자릿수 미만인 자연수입니다.

📌 풀이 과정 

✅ #사용된 개념: 탐욕법 (Greedy) 

• 지금 당장 최선의 선택을 하는 것 => 최적의 해는 X 
• 난이도가 높아지면 정렬, 스택, 큐를 사용해 풀이되기도 한다.
• 최단 경로를 구하는 다익스트라 알고리즘은 그리디 알고리즘으로 분류 되므로 암기가 필요한 알고리즘 이다.
• 문제에 따라 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 알게 모르게 제시해 준다.
• 어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자.
• 만약 오랜 시간을 고민해도 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 그때는 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지 재차 고민해보는 것도 한 방법이다

✅ # 아이디어 

1. from itertools import combination => 시간 초과 될 것 같아서 PASS
2. number[i] >= number[i+1]인 경우에만 answer에 추가한다. 단, k를 채울 때까지! 
3. (구글링 후) 스택으로 구현해야 가능하구나 

✅ #첫번째 시도 : FAIL

## 예시1. numbers = "1231234" k = 3일때 

1 < 2 => 1 제거 answer = "" 
2 < 3 => 2 제거 answer = ""
3 > 1 => 3 추가 answer = "3"
1 < 2 => 1 제거 answer = "3" ==> k = 3 만족 

나머지 "234"를 answer에 추가해준다. 

## 예시2. numbers = "4177252841" k = 4 일 때 
4 > 1 => add 4 
1 < 7 => del 1 
7 = 7 => add 7 
7 > 2 => add 7 
2 < 5 => del 2 
5 > 2 => add 5 
2 < 8 => del 2 
8 > 4 => add 8 
4 > 1 => add 4 => answer = "477584"
--> 마지막 i == len(numbers)-1 이고 k = 3 이므로 
--> answer += numbers[i] 
--> answer = "4775841" 에 대해서 
1. i = 0 reset
2. number = answer
3. 위의 과정 반복

 

=> 문제점: del_cnt와 number[i] 비교까지는 좋았지만, 다음 stage로 넘어갈 때 number가 변경된 number로 실행되어야 하는데 그거 구현을 실패함. 

• number[i] >= number[i+1] 일 때 answer에 붙이는 방법을 시도했다. 
• 반대일 경우에는, number[i]를 추가하지 않으므로 del_cnt +=1 한다.
• del_cnt == k 인 경우
  • numbers 한 바퀴 다 돌기 전이라면 number[i:]를 answer에 붙여준다. 
  • 한 바퀴 이상 돌고 나서인 경우에는, number[i]만 answer에 붙여준다. 
• del_cnt < k 인 경우 
  
  • numbers 한 바퀴 다 돈 경우
    • answer += number[i:] (남은 거 일단 붙임)
    • i = 0 으로 리셋

def solution(number, k):
    answer = ''
    del_cnt = 0 
    i = 0
    stage = 0 
    while True: 
        if 0<=i<len(number)-1:
            if number[i] >= number[i+1]:
                answer += number[i]
                # print(f'ADD {number[i]} answer = {answer}')
            else: 
                del_cnt += 1
                # print(f'DEL {number[i]} del_cnt = {del_cnt}')
            i += 1
        if del_cnt == k:
            if i <= len(number)-1 and stage == 0:  # 다 돌기도 전에 만들어진 경우 
                answer += number[i:]   # 나머지 number[i] 다 붙이기 
                break 
            elif i <= len(number)-1 and stage > 0:
                answer += number[i]
                break 
        elif del_cnt < k:   
            if i == len(number)-1:  # 한 바퀴 다 돌았는데도 아직 다 못 제거한 경우
                answer += number[i:]   # 나머지 number[i] 다 붙이기 
                i = 0               # 맨 첨으로 가서 다시 거름
            	number = answer     # 이때 한번 걸러진 걸로다가 
       stage += 1


    return answer

 

✅ # 두번째 시도: 구글링 

• 스택을 이용해 풀 수 있다는 걸 확인했다. 
• 기준: 추가하려는 수는 반드시 맨 위의 숫자보다 작아야 한다. == 맨 위의 숫자 < 추가 숫자 ==> 맨 위 숫자 pop 

1. 스택에 number[0] 넣고 시작 
2. number 안에 각 요소 n에 대해서 스택 안에 n보다 작은 숫자는 전부 뺄거야
   • while 문: 스택 맨 위의 숫자 answer[-1] < 지금 추가하려는 수 n 일 때 
     • pop(-1) 하고 k -= 1
     • 이때 k<0이 되면 그만 pop해야 하니 break 
   • n보다 작은 수 다 뺏으면 append(n)
3. for문이 끝났는데도 k가 남으면 이미 number[i] > number[i+1]로 정렬되어 있단 뜻이므로 뒤에서 k개를 떼어줘야 한다. 이때 if문이 실행되고 아닌 경우에는 answer 그대로 return

🍀 # 배운 점 

1. 그리디 알고리즘인지 확신하고 풀 수 있을지는 모르지만, 가장 큰 수, 가장 작은 수를 만들어야 할 때 자료구조를 활용하는 방법도 있다는 걸 잊지 말기

📌 풀이 코드 

def solution(number, k):
    answer = [] # stack 
    for n in number: 
        if answer == []:        # 1. 맨 처음에는 일단 추가 
            answer.append(n)
            continue
        # 2. 지금 추가하려는 수: n 
        if k > 0:
            while answer and answer[-1] < n:   # 스택안에 n보다 작은 숫자는 전부 뺄거야
                answer.pop(-1)
                k -= 1
                if k <= 0:
                    break 
        answer.append(n)    # if문 안에 들어가버리면, k값이 0이 되었을 때 남은 숫자는 추가를 못해줘.
    # 3. for문이 끝났는데도 k가 남는 경우: numbers="54321" k=2 일 때 
    if k > 0: # 뒤에서 k개를 떼어내줘야 해 
        return ''.join(answer[:len(number)-k])
    else: 
        return ''.join(answer)

 

✅ 테스팅 케이스 참고