명똥 알고리즘/알고리즘 실습
Python - 알고리즘 실습 : 프로그래머스 <큰 수 만들기>
민빵명똥
2023. 11. 2. 23:06
반응형
오늘은 그리디 알고리즘 문제였던 프로그래머스 큰 수 만들기 문제다!! 그리디는 아이디어가 필요한 문제 같다.. 그렇지만 간단하고 직관적이기 때문에 구현이 쉽고 실행속도도 빠르다.
그렇기 때문에 그리디 문제의 특징이 있다. 잘못된 알고리즘을 선택하면 시간 초과가 날만큼 배열 길이가 큰 것!!
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
1. 프로그래머스 큰 수 만들기
1) 문제 요약
(1) number 가 주어지면 k번 숫자를 지울 수 있는데 k번을 다 소모하여 최대 숫자를 얻는다.
(2) number는 100만 자리 이하 숫자이다.
→ 그리디 알고리즘
2) 문제 해결
(1) 숫자를 하나씩 고르면서 모으고 작은 것을 제거해 주어야 하기 때문에 stack을 사용한다.
def solution(number, k):
n = len(number)
arr = list(map(int, number)) # number 리스트로 만들기 // 혹시 몰라서
stack = []
i = 0
while True:
if not stack: # 스택이 비면, 무조건 추가
stack.append(arr[i])
i += 1
elif stack:
# 스택에 숫자가 있고 (IndexError)// 스택 끝 숫자보다 다음 숫자가 더 클때, 제거 기회가 있으면 => 제거
while len(stack) > 0 and stack[-1] < arr[i] and k > 0:
stack.pop()
k -= 1
# 만약 스택이 비어 있거나 (IndexError)// 스택 끝 숫자보다 다음 숫자가 작거나 같을 때,
k == 0일 때는 무조건 append
if len(stack) == 0 or k == 0 or stack[-1] >= arr[i]:
stack.append(arr[i])
i += 1
if i == n: # 끝까지 오면 break
break
# k가 남아 있으면 무조건 뒤에서부터 k 만큼 제거
if k != 0:
stack = stack[:-k]
answer = ''.join(map(str, stack))
return answer
그리디 알고리즘은 어떻게 문제를 풀 것인가에 대한 아이디어 도출이 제일 중요한 것 같다. 그냥 알고리즘보다 이해하기가 힘든 부분이 있었다.
코드도 지저분해진 것 같다. 왜냐하면 IndexError 처리를 위해 조건을 추가했고, 겹치는 조건들도 보이는 것 같다.
반응형