링크

큰 수 만들기

문제 요약

  • 숫자에서 k개의 숫자를 제거하여 최대의 숫자를 만들기.

초반 접근

  • 모든경우 확인 - 런타임 에러
  • 반복문을 통해 앞에서부터 숫자가 커지면 앞에숫자 삭제, 작아지면 뒤에숫자 삭제로 진행
    • 일부 경우에서 실패
  • 각 지점마다 k길이 만큼 잘라서 큰값 찾기
    • 런타임 에러

해결법

  • 최대한 한번에 하려고 생각했었음
  • 엄청 복잡한 알고리즘이라 생각하고 구현하려 했음
  • 하지만 큰값을 찾아내는 과정은 좌측에서 시작하여 우측으로 진행되는게 아닌, 우측에서 좌측으로 진행되는것임
  • [3,2,1,5]가 있으면 5를 기준으로 좌측방향으로 순서대로 지우면 최대값을 만들수 있음
    • 1개를 지우면 [3,2,5], 2개를 지우면 [3,5], 3개를 지우면 [5]
  • 이러한 알고리즘방식을 적용하기위해서는 스택(Stack)구조로 해결이 가능

알고리즘 간단 정리

  • 스택에 하나씩 push한다.
  • 스택의 top과 넣을 요소를 비교한다.
    • top<넣을 요소인 경우
      • 넣을 요소가 더 크다
      • 만약 k가 0이되면
        • stack에 push만 해준다.
      • k가 0보다 크면
        • stack에서 (top>넣을요소)가 될때까지 pop한다.
        • pop할때 k도 하나씩 지워준다.
    • top>=넣을 요소인 경우
      • stack에 push한다.
  • k가 남으면 stack의 끝부분을 k만큼 삭제한다.

후기

  • 이 문제는 너무 복잡하게 생각하다가 어려워진 문제이다.
  • 사이트에서 정해준 레벨은 낮은편이어서 만만하게 보았다가 머리 터지는줄 알았다.
  • 알고보니 기존에 배운 자료구조를 활용하는 단계였지만, 문제의 풀이에서 바로 떠오르지 못하였다.
  • 문제를 보았을때 문제의 예시와, 직접 문제를 푸는 패턴을 파악하여 알고리즘화 하는 연습이 부족하다고 생각한다.
  • stack이라는 키워드를 힌트로 바로 풀린게 간단하면서 기초를 요구한 문제였다.
  • 최대한 문제 패턴을 파악하자(낮은 난이도면 대부분 풀림)

출처

  • 스택힌트