이숭간 공부기록
[프로그래머스] 파이썬 _ 큰 수 만들기 본문
728x90
https://programmers.co.kr/learn/courses/30/lessons/42883
문제유형 : 그리디
문제풀이 :
- 스택을 이용한다. ( 숫자의 맨앞을 계속해서 더 크게 만들어주는것 )
- 스택에 숫자가 있고 k가 0 이상이면 현재숫자와 비교해서 더 큰값이 스택의 앞쪽에 위치할 수 있도록 한다.
- 만약 현재숫자가 현재스택 최상단숫자보다 작으면 그냥 넣는다.
- 현재숫자가 더 크다면 스택에서 pop하고 k를 1감소시킨다. 이 과정을 더이상 스택의 최상단에서 현재숫자보다 큰값이 안나올때가지 반복한다.
- 숫자를 모두 확인했는데 k가 0이상이면 더 제거해야한다는 뜻이고, 이미 앞쪽에는 최대한 큰 숫자가 앞에 위치하도록 조정해 놓은것이므로 뒤에서부터 k만큼 삭제하도록한다.
정답코드 :
def solution(number, k):
answer = ''
stack = []
# 스택에 숫자가 있으면 현재숫자와 비교해서 현재가 더 크면 빼고 k도 -1
# 제일 큰 숫자가 맨 앞이 되도록 조저한다.
# 현재숫자가 더 작으면 스택에 넣는다.
# k=0이면 그만한다.
# k가 0이상이면 number를 줄인다.
for i in number:
if stack and k>0:
# 아직 잇고 상단값이 현재값보다 작으면 계쏙반복
while stack and stack[-1] < i and k>0:
stack.pop()
k -= 1
stack.append(i)
else: #스택이 비어있거나 k가 0이라서 더이상 줄일수가 없을때
stack.append(i)
if k >0:
for _ in range(k):
stack.pop()
return ''.join(stack)
백준의 2812번_ 크게만들기와 똑같다.
https://www.acmicpc.net/problem/2812
import sys
input = sys.stdin.readline
k,n = map(int, input().split())
number = input().strip()
s =[]
#1924
for i in number:
if not s or n == 0: #s가 비어있으면
s.append(i)
else:
while s and s[-1] < i and n>0:
s.pop()
n -= 1
s.append(i)
if n>0:
s = s[:len(s)-n]
print(''.join(s))
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 파이썬 _N으로 표현 (0) | 2021.07.15 |
---|---|
[프로그래머스] 파이썬 _ 이중 우선순위 큐 (0) | 2021.07.15 |
[프로그래머스] 파이썬 _ 등굣길 (0) | 2021.07.12 |
[프로그래머스] 자바/파이썬 _ 기능개발 (0) | 2021.07.09 |
[프로그래머스] 파이썬 _ 뉴스 클러스터링 (0) | 2021.07.08 |