현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘. 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있으면 매우 효과적이고 직관적인 알고리즘이지만, 대부분의 문제에 대해서는 "최적의 해"를 찾을 수 없는 가능성이 크기 때문에 주의해서 사용해야 하는 알고리즘입니다. 매 순간의 선택은 그 순간에 대해서는 최적이었을지라도 그것이 결론적으로 최적이 아닐 수 있기 때문입니다. 그렇기 때문에 그리디 알고리즘을 이용해 문제를 해법을 찾을 경우, 그 해법이 정당한지에 대해서 반드시 확인해 보아야 합니다.
대표적으로 거스름돈 문제가 있으며 다익스트라 알고리즘 또한 그리디 알고리즘이라고 할 수 있습니다.
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
number | k | return |
---|---|---|
"1924" | 2 | "94" |
"1231234" | 3 | "3234" |
"4177252841" | 4 | "775841" |
문자열로 주어진 숫자에 대해서 k개의 수를 제거하여 가장 큰 수가 되도록 만드는 문제입니다.
접근 방식만 잘 생각하면 10줄 내외로 풀이 할 수 있는 비교적 간단한 문제였지만, 알고리즘 문제 풀이를 시작한 지 얼마 되지 않아 많이 헤맸던 문제이기도 합니다.
시간 초과가 났던 풀이 방식입니다. 실제로도 제한 조건이 100만 자리 이하의 자연수이기 때문에 시간 초과가 날 것을 예상하긴 했지만 가장 단순한 접근이라서 풀어보았습니다.
문제의 핵심은 k개의 수를 제거한 후, 가장 큰 수를 구하는 것이기 때문에 k개를 제외한 나머지 수를 순서와 상관없이 뽑는 모든 경우의 수에서 최댓값을 구하면 된다고 생각하여 조합을 활용 후 정렬하여 결괏값을 구할 수 있었습니다.
from itertools import combinations
def solution(number, k):
answer = list(combinations(list(number), len(number)-k))
return ''.join(sorted(answer, reverse = True)[0])
단순하게 접근해서 앞에서부터 i번째와 i+1번째 수를 비교해서 number[i] < number[i+1] 일 경우 number[i]를 총 k번 삭제하는 방법을 생각해 보았습니다. (number[i] == number[i+1] 일 경우에는 i++)
하지만, 이 경우에는 입출력 예시 1924와 1231234의 경우는 정답을 찾을 수 있지만 4177252841과 같은 경우는 결과가 772841이 되어서 정답을 찾을 수 없었습니다. (대충 테스트해 본 것이라 그 외에도 문제가 많긴 합니다;;)
def solution(number, k):
number = list(number)
i = 0
while k > 0:
start = number[i]
end = number[i+1]
if(start != end):
if(start < end):
del number[i]
k -= 1
else:
del number[i+1]
k -= 1
else:
i += 1
return ''.join(number)
앞선 접근 실패 후, 여러 고민을 해봤지만 다른 접근 방식이 떠오르지 않아서 안 될 것을 알면서도 한 번 시도해본 방식입니다... 숫자는 0~9까지로 이루어져 있으니까 큰 수를 만들려면 작은 수부터 제거해보자는 생각으로 number에 포함된 0~9까지 수의 개수를 count 한 후 0부터 시작해서 k개만큼을 제거해 보았습니다.
결론적으로 이 방식도 전체에서 작은 수를 제거하는 것이 아닌 앞에서부터 작은 수를 제거해서 큰 수를 만들어야 하는데 그렇지 못해서 실패한 방식입니다.
def solution(number, k):
digit_count = dict()
for i in range(10): # 0부터 9까지
count = number.count(str(i))
if(count != 0):
digit_count[i] = count
for key in digit_count.keys():
if(k <= 0):
break
count = digit_count[key]
if(count <= k):
number = number.replace(str(key), '')
k -= count
else:
number = number.replace(str(key), '', k)
break
return number
마지막 시도로 살짝 구글링을 통해 힌트를 얻고 풀이를 진행하였습니다. 앞선 시도에서는 제거에만 초점을 두고 문제를 풀이하였는데 Stack
을 활용해서 문제를 풀 수 있다는 것을 알게 되니까 push
와 pop
두 가지를 사용해서 풀이하는 방식을 생각해 보았습니다.
push
할 값보다 작다면 크거나 같은 값이 나올 때까지 값들에 대해서 pop
을 하는 것입니다. O(n)
의 시간 복잡도로 문제를 해결할 수 있습니다.for num in number:
pop
push
join
해서 결과 값 반환앞자리에 큰 숫자가 오는 것이 전체 수를 크게 만들 수 있습니다.
number = "4177252841", k=4일 경우,
number = "999", k=2일 경우,
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)
1차 코드에서 중복되는 부분이나 불필요한 부분을 줄이고 최적화된 코드로 작성해보았습니다.
def solution(number, k):
answer = [] # Stack
for num in number:
while k > 0 and answer and answer[-1] < num:
answer.pop()
k -= 1
answer.append(num)
return ''.join(answer[:len(answer) - k])
def solution(number, k):
answer = [] # Stack
for num in number:
while k > 0 and answer and answer[-1] < num:
answer.pop()
k -= 1
answer.append(num)
return ''.join(answer[:len(answer) - k])
Stack
을 활용하기I vow I'll read your stuff more frequently. snake io is a game that I recently learned about, and anytime you have some free time, I'd love for you to play it with me.
감사합니다