공부 기록장
백준 2812. 크게 만들기 본문
https://www.acmicpc.net/problem/2812
2812번: 크게 만들기
N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
코드
n, k = map(int, input().split())
num = list(map(int, input()))
st = [num[0]]
for i in range(1, len(num)):
while len(st) > 0 and k > 0:
if st[-1] < num[i]:
st.pop()
k -= 1
else:
break
st.append(num[i])
if k > 0:
print(''.join(map(str, st[:-k])))
else:
print(''.join(map(str, st)))
문제를 읽고,1부터 9까지 작은 수부터
앞에 있는 숫자부터 지우면 되겠다고 생각했다.
하지만 해당 방식은 예제 3번과 같은 경우 때문에 해답이 아니었다.
더 고민을 하다가
1부터 9까지 작은 수부터 시작을 해서 뒤로 가면서 해당 작은 수보다
큰 수가 있으면 해당 수를 삭제하면 되겠다고 생각했다.
근데 구현을 하다가 실패했고,
다른 분들의 코드를 참고했다.
주어진 숫자들을 앞에서부터 스택에 하나씩 넣으면서
스택에 가장 최근에 들어온 값과 새로 들어온 값을 비교해
스택에 들어 있는 값이 더 작으면 pop 해 주는 논리를 사용해 풀면 풀리는 문제였다.
문자들을 다 훑고 반복문을 나왔는데
k가 여전히 양수인 경우에는
스택의 뒤에서 k 만큼의 숫자를 제외한 나머지를 출력해준다.
참고 자료
https://yuna0125.tistory.com/52
[백준] #2812 크게 만들기 (python)
2812번: 크게 만들기 (acmicpc.net) 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 N자리 숫자가
yuna0125.tistory.com
[Python] 백준 2812번: 크게 만들기
https://www.acmicpc.net/problem/2812프로그래머스 Level2 큰 수 만들기와 동일한 문제numbers에 있는 숫자를 하나씩 stack에 넣고 그 다음 숫자와 비교만일 다음 숫자가 stack에 있는 숫자보다 크면 stack.pop()
velog.io
'코딩 테스트 > 백준 문제 풀이' 카테고리의 다른 글
| 백준 11404. 플로이드 (0) | 2024.01.23 |
|---|---|
| 백준 13549. 숨바꼭질3 (0) | 2024.01.23 |
| 백준 2138. 전구와 스위치 (0) | 2024.01.22 |
| 백준 13975. 파일 합치기 3 (0) | 2024.01.22 |
| 백준 12904. A와 B (0) | 2024.01.20 |