[BOJ2812] 크게 만들기

2812번: 크게 만들기

가장 큰 수가 되는 조건이 무엇인지 찾아야 한다 -> 그리디적 사고방식.

• 맨 앞에 있는 숫자가 최대한 클 수록 유리하다. 그러므로 그렇게 만들어야 한다.
• 스택 자료구조를 이용한다.
  • 내가 있는 위치를 기준으로 다음에 들어갈 원소가 나보다 크다면
    • 다음에 있는 원소가 기준이 되고,
    • 1. 다음에 있는 원소에서 이전을 검사하여 큰 값을 만날 때까지, K > 0일 때까지
    • 1. 이전 원소들을 빼본다.
  • 그게 아니라면 그냥 스택에 푸쉬한다.
• 위의 과정을 거쳤는데 아직 K번을 다 뺀 상황이 아니라면 뒤에 붙은 원소들은 자연스럽게 작은 원소들임.
  • 맨 뒤에서부터 K가 0이 될 때까지 스택을 pop한다.
• 이후 스택에 있는 원소를 reverse()하여 답을 출력한다.

 

GitHub - ssjjaa-algo/AlgoAndMySQL