[백준] No.2812 - 크게 만들기 (C++)

문제

 

https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

 

풀이

 

solved.ac 난이도: Gold 5

 

 

 

자료구조, Stack을 활용하는 그리디 문제.

 

그리디 문제들에는 특히 자료구조를 이용하는 경우가 많은 것 같다.

취업을 위해 치르는 코딩 테스트들에도 그리디 문제가 특히 많이 출제되는데, 그 배경에는 자료구조에 얼마나 익숙한지 보기위함도 없잖아 있지 않을까? 라는 생각이든다.

 

스택을 이용한 풀이를 떠올리지 못하여 N~N-K 번째 수중에 가장 큰 것(idx)을 고르고, 다시 그 수부터 idx ~ idx - k +1 번째 수 중에서 가장 큰수를 고르는 것을 반복하려하였다.

이런 경우 시간 복잡도는 O(N^2)이기 때문에 N=500,000인 경우 시간안에 계산하기 힘들다.

 

  하지만 스택을 활용하면 O(N)의 복잡도만에 해결할 수 있었다...

해당 풀이는 아래와 같다.

 

현재 숫자(idx번째)가 stack.top보다 크다면 idx 수보다 크거나 같은 수가 나올때까지 stack.pop해준다.

(pop을 할 때는 지울 수 있는 숫자 수(erasable_num)를 하나씩 줄여주자.)

pop이 완료 되면, stack에 해당 숫자를 push해준다.

 

이를 지울 수 있는 숫자 수(erasable_num)가 0이 될때 까지 반복해주면 K개의 수를 지운 가장 큰 수가 완성된다.

 

예를 들어 아래의 입력인 경우

 

6 3

765789

 

스택의 상태는 아래와 같이 진행된다.

 

erasable_num:3	3	3	1	0	0
		5			9
	6	6	7	8	8
7	7	7	7	7	7

 

 

 

추가적으로 이러한 예제의 경우 처럼

 

6 3

654321

 

 숫자가 내림차순으로 주어진다면 stack.pop을 할 조건을 만족하지 못하여 숫자가 삭제되지 않고 stack에 쌓일 수 있다.

 

따라서 erasable_num> 0인 경우 0이 될때까지 위의 값을 pop해주도록 하자.

 

최종적으로 정답은 stack의 역순으로 출력해준다.

 

코드