728x90
풀이 1 : 조합 (실패)
from itertools import combinations
def solution(number, k):
numList = list(number)
data = list(range(0, len(numList)))
maxNum = 0
answer = ''
delete = list(combinations(data, k))
for row in delete:
tempList = numList.copy()
for i in row:
tempList[i] = ''
tempNum = int(''.join(tempList))
if maxNum < tempNum:
maxNum = tempNum
answer = str(maxNum)
return answer
- 조합으로 삭제 가능한 모든 인덱스 조합을 delete 배열에 저장하고 이중 반복문을 돌면서 가장 큰 숫자를 찾았다.
- 주어진 테스트 케이스는 통과했으나, 제출하면 시간 초과로 실패가 떴다.
풀이 2 : stack (성공)
def solution(number, k):
stack = []
answer = ''
for n in number:
while stack and stack[-1] < n and k != 0:
stack.pop()
k -= 1
if len(stack) < len(number) - k:
stack.append(n)
answer = ''.join(stack)
return answer
힌트 참고
- stack(fifo)을 이용해서 문제를 해결했다. stack 안에는 만들 수 있는 가장 큰 수가 최종적으로 들어간다.
- number를 반복문으로 돌면서 stack을 채운다.
- k는 삭제할 수이며 stack에서 pop할 때마다 k를 1씩 빼준다.
- n에 대해 stack 안에 값이 있고, stack의 마지막 값이 n보다 크며 k가 0이 아니라는 조건이 만족한다면 계속 stack을 pop 해준다.
- while문을 빠져나온 뒤, stack의 길이가 만들어져야할 숫자의 길이보다 작을 때 n을 append한다.
반응형
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스 코딩테스트 고득점 Kit / 탐욕법(Greedy)] 구명보트 (python) (0) | 2024.03.07 |
---|---|
[프로그래머스 코딩테스트 고득점 Kit / 탐욕법(Greedy)] 조이스틱 (python) (0) | 2024.03.04 |
[프로그래머스 코딩테스트 고득점 Kit / 탐욕법(Greedy)] 체육복 (python) (0) | 2024.02.29 |
[프로그래머스 코딩테스트 고득점 Kit / 힙(Heap)] 이중우선순위큐 (python) (0) | 2024.02.28 |
[프로그래머스 코딩테스트 고득점 Kit / 힙(Heap)] 더 맵게 (python) (0) | 2024.02.20 |