[백준] 2812. 크게 만들기
문제
풀이
방법 : 큰 수를 만날 때 까지 index를 넘기다 큰 수를 만나면 큰 수의 직전 수를 제거함.
ex) 1) 4177252841 > 2) 477252841 > 3) 77252841 > 775841
문자열로 풀다가 시간초과 나서 스택으로 해결함.
1. alive, dead, num 3가지 배열을 사용함.
2. 일단 무조건 alive stack이 비어있으면 num[0]를 popleft해서 alive에 append 해줌.
3. 그리고 alive[-1]과 num[0]를 비교해줌.
- alive[-1] >= num[0] : 큰 수를 못 만났기 때문에 num[0]를 popleft해서 append 해줌.
- alive[-1] < num[0] : 큰 수를 만났기에 alive[-1]을 pop하여 dead로 append 해줌.
- 이렇게 pop하면서 while문의 조건을 만족시키면 dead를 제외한 alive + num을 print해주면 됨.
하지만, 위 코드는 n, k = 3, 2 / 523 같은 num이 판단을 미쳐 다 하기전에 비워지는 반례가 생김. 따라서 num의 크기가 0이 되면, alive에서 k - dead만큼 alive에서 pop하여 dead에 추가해줌.
(∵ num이 빌때까지 dead를 못 채웠단 소리는 큰 수를 계속 못 만났다는 소리고, 이는 곧 alive가 내림차순으로 구성되어 있음을 알 수 있음. 따라서, dead의 부족 분 만큼 pop을 해주면 가장 큰 수를 얻을 수 있음.)
코드
import sys
from collections import deque
def solution() :
n, k = map(int, sys.stdin.readline().split())
num = deque(list(input()))
alive = []
dead = []
while len(dead) != k :
if len(num) == 0 :
for _ in range(k - len(dead)) :
alive.pop()
break
if len(alive) == 0 :
alive.append(num.popleft())
else :
if alive[-1] >= num[0] :
alive.append(num.popleft())
else :
dead.append(alive.pop())
print(''.join(alive + list(num)))
solution()
Author And Source
이 문제에 관하여([백준] 2812. 크게 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@tldjfj123/백준-2812.-크게-만들기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
방법 : 큰 수를 만날 때 까지 index를 넘기다 큰 수를 만나면 큰 수의 직전 수를 제거함.
ex) 1) 4177252841 > 2) 477252841 > 3) 77252841 > 775841문자열로 풀다가 시간초과 나서 스택으로 해결함.
1. alive, dead, num 3가지 배열을 사용함.
2. 일단 무조건 alive stack이 비어있으면 num[0]를 popleft해서 alive에 append 해줌.
3. 그리고 alive[-1]과 num[0]를 비교해줌.
- alive[-1] >= num[0] : 큰 수를 못 만났기 때문에 num[0]를 popleft해서 append 해줌.
- alive[-1] < num[0] : 큰 수를 만났기에 alive[-1]을 pop하여 dead로 append 해줌.
- 이렇게 pop하면서 while문의 조건을 만족시키면 dead를 제외한 alive + num을 print해주면 됨.
하지만, 위 코드는 n, k = 3, 2 / 523 같은 num이 판단을 미쳐 다 하기전에 비워지는 반례가 생김. 따라서 num의 크기가 0이 되면, alive에서 k - dead만큼 alive에서 pop하여 dead에 추가해줌.
(∵ num이 빌때까지 dead를 못 채웠단 소리는 큰 수를 계속 못 만났다는 소리고, 이는 곧 alive가 내림차순으로 구성되어 있음을 알 수 있음. 따라서, dead의 부족 분 만큼 pop을 해주면 가장 큰 수를 얻을 수 있음.)
코드
import sys
from collections import deque
def solution() :
n, k = map(int, sys.stdin.readline().split())
num = deque(list(input()))
alive = []
dead = []
while len(dead) != k :
if len(num) == 0 :
for _ in range(k - len(dead)) :
alive.pop()
break
if len(alive) == 0 :
alive.append(num.popleft())
else :
if alive[-1] >= num[0] :
alive.append(num.popleft())
else :
dead.append(alive.pop())
print(''.join(alive + list(num)))
solution()
Author And Source
이 문제에 관하여([백준] 2812. 크게 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@tldjfj123/백준-2812.-크게-만들기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
from collections import deque
def solution() :
n, k = map(int, sys.stdin.readline().split())
num = deque(list(input()))
alive = []
dead = []
while len(dead) != k :
if len(num) == 0 :
for _ in range(k - len(dead)) :
alive.pop()
break
if len(alive) == 0 :
alive.append(num.popleft())
else :
if alive[-1] >= num[0] :
alive.append(num.popleft())
else :
dead.append(alive.pop())
print(''.join(alive + list(num)))
solution()
Author And Source
이 문제에 관하여([백준] 2812. 크게 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tldjfj123/백준-2812.-크게-만들기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)