https://www.acmicpc.net/problem/2812
2812번: 크게 만들기
N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
소스코드
풀이
★ k개를 제거하여 가장 큰 수를 만들어야 하기 때문에 수들을 stack에 넣어가며 대소비교를 해줘야 합니다. stack 안에 들어있는 값보다 비교하려는 값이 더 작다면 그 수는 stack에 들어올 수 없습니다.
★ for문을 돌면서 stack이 비어있지 않고, 제거해야 하는 갯수인 k가 0보다 크다면 stack의 최상단 값과 반복문을 도는 값의 크기 비교를 해줍니다. 만약 stack안에 있는 값이 작다면 pop으로 제거해주고, k또한 -1 해줍니다. 크다면 while문을 빠져나간 뒤 stack에 해당 값을 append 해줍니다.
★ 위와 같은 과정을 반복하게 된다면 예시 케이스는 물론 정답 또한 75%까지 맞는 걸 확인할 수 있습니다. 하지만 100%가 나오지는 않는데 반례로 n = 2, k =1, a= 21일 경우 답은 2가 되어야 하지만 21이 나옵니다. 그 이유는 stack에 처음 들어가는 값인 2가 그 다음 값인 1보다 크기 때문에 while문 안에 있는 if문의 조건이 성립하지 않기 때문입니다.
★ 그렇기에 반복문을 다 돌았을 때 여전히 k 값이 0보다 크다면, k의 값 만큼 stack의 최상단부터 pop 해줘야 합니다. 왜냐하면 stack의 앞부분부터 큰 수가 들어가 있기 때문에 가장 큰수를 만들어주기 위해서입니다 !
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 10815번: 숫자카드 (Python) (0) | 2023.06.05 |
|---|---|
| [백준 알고리즘] 1920번: 수 찾기 (Python) (0) | 2023.06.05 |
| [백준 알고리즘] 3986번: 좋은 단어 (Python) (0) | 2023.06.03 |
| [백준 알고리즘] 17608번: 막대기 (Python) (0) | 2023.06.03 |
| [백준 알고리즘] 5397번: 키로거 (Python) (0) | 2023.06.03 |