[Python | week1-4] 그리디 알고리즘(Greedy Algorithm) |

week 1-4

 

1-1부터 현재 글(1-4)까지 매번 작성한 글은

4주차, 즉 week 4까지 작성 될 예정입니다.

 

프로그래머스 School 에서 진행하는 코테 준비 강의로

본 과정을 더욱 깊이 이해하기 위해서 스스로 작성하는 시리즈입니다

 

 

 

 

week1-2 에서 학습한 그리디 알고리즘이 또 다시 등장했습니다!

 

2023.01.13 - [📂Language/Python] - [Python | week1-2] Greedy 알고리즘 | 이것이 코딩테스트다

[Python | week1-2] Greedy 알고리즘 | 이것이 코딩테스트다

하지만 제가 이 문제를 해결하진 못 했습니다ㅠ

당시에는 완벽히 이해했다고 생각했지만..

 

알고리즘을 알고 있는 것과 적용하여 해결 할 수 있는 것은

별개의 문제라는 것을 깨달았습니다..!

 

 

 

 

---

 

다짜고짜 문제부터 들어갑니다.

# [문제 설명]
# 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
#
# 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
#
# 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다.
# number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
#
# [제한 조건]
# number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
# k는 1 이상 number의 자릿수 미만인 자연수입니다.

스스로 단계적으로 생각하여 알고리즘을 작성하는데 어려움이 있어서

강의를 보고서 다시 작성했는데, 그 과정을 다시 같이 살펴봅시다!

 

 

1. 문제 이해하기

최종적으로 주어진 수에서 가장 큰 값을 추출하고싶습니다!

현재의 선택이 최종 선택에 영향을 주지 않습니다..!

그렇다면 어떤 알고리즘을 사용할 수 있을까요?

 

네 그리디 알고리즘입니다!

앞단계 에서의 선택(앞자리에 큰 수)이 이후 단계에서의 

동작에 대한 해(solution)의 최적성에 영향을 미치지 않음 

 

 

collection이라는 리스트를 최적의 결과를 담도록 사용할 것입니다.

해당 리스트에는 매 번의 순간마다 최선의 선택을 한 경우가 저장 될 것입니다.

 

문제로 제시된 number를 순차적으로 돌면서 (자릿수가 높은 것에부터) 비교합니다.

다음 자릿수가 저장된 collection보다 더 크다면, 작지 않을 때까지 collection의 마지막 원소를 제거합니다.

 

def solution(number, k):
	collection = []
    for i, n in enumerate(number):
    	while len(collection) > 0 and collection[-1] < k:
        	collection.remove(collection[-1]) #이후 수정 예정
            k -= 1
        collection.append(n)
        
    answer = ''.join(collection)

 

2. 고려 사항

위와 같은 코드로 해결 가능할까요?

고려사항은 다음과 같습니다.

 

1) 자릿수를 모두 제거해야할 수(k)가 0이 됐을 때

더이상 제거할 수 있는 개수(k)가 없다면 while문을 종료함으로 더이상 값을 제거하면 안 됩니다.

def solution(number, k):
	collection = []
    for i, n in enumerate(number):
    	while len(collection) > 0 and collection[-1] < k and k > 0: #조건으로'k>0' 추가됨
        	collection.remove(collection[-1]) #이후 수정 예정
            k -= 1
        collection.append(n)
        
    answer = ''.join(collection)

2) 제거해야할 수가 남은채로 모든 자릿수를 다 돌았을 때

def solution(number, k):
	collection = []
    for i, n in enumerate(number):
    	while len(collection) > 0 and collection[-1] < k and k > 0:
        	collection.remove(collection[-1]) #이후 수정 예정
            k -= 1
        if k == 0: #추가된 코드
        	collection += number[i:] #현재 자리수부터 끝까지 붙이기
            break
        collection.append(n)
        
    answer = ''.join(collection)

3) 리스트 끝에 값을 넣고 빼기

리스트 끝에 값을 넣을 때는 append를 사용하는 것이 맞지만

값을 제거할 때는 어떨까요?

collection.remove(collection[-1]) 해당 코드가 효율적일까요?

 

그렇지 않습니다.

collection[-1]의 값을 찾고 그 값을 다시 리스트에서 찾아서

제거하는 과정을 거치므로 효율적이지 않습니다.

 

리스트의 마지막 원소를 제거하고 싶다면

list.pop()을 통해서 더욱 빠르게 구현할 수 있습니다.

 

def solution(number, k):
	collection = []
    for i, n in enumerate(number):
    	while len(collection) > 0 and collection[-1] < k and k > 0:
        	collection.pop() #수정된 코드
            k -= 1
        if k == 0: #추가된 코드
        	collection += number[i:]
            break
        collection.append(n)
        
    answer = ''.join(collection)

 

 

[최종 코드]

def solution(number, k):
	collection = []
    for i, n in enumerate(number):
    	whlie len(collection) > 0 and collection[-1] < n and k > 0:
        	collection.pop() #list의 마지막 값
            k -= 1
        if k == 0: #더이상 제거할 수 있는 개수가 없을 때
        	collection += number[i:] #number의 i번째부터 끝까지 붙이기
            break #반복문에서 효율성을 향상시킬 수 있는 방안 중 하나
        collection.append(n)
        
    answer = collection[:-k] if k > 0 else collection #제거해야할 개수(k)가 남았을 때 맨 뒤 k개를 제거
    return ''.join(answer)