[프로그래머스] 42883 큰 수 만들기

프로그래머스 level2

문제

문제 풀이

문제 리뷰

탐욕법(Greedy)

그리디 알고리즘은 동적 프로그래밍 사용 시, 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다.

동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 보완하는 개념

• 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법
  

  탐욕 알고리즘, 욕심쟁이 알고리즘
  

---

처음에는 배열을 이용하여 i, i + 1번째를 비교하여
둘 중 작은쪽을 삭제하는식으로 구현하려고 했으나
인덱스가 꼬이는 부분들이 발생하여 몇몇 케이스를 통과하지 못했다.
다른 분들의 풀이를 참고했으나 쉽게 다가오지 않아
몇몇분들이 스택으로 많이 구현을 하셨길래 스택으로 구현해보았다.

스택은 후입선출의 원리를 갖는다.

가장 나중에 들어온 데이터가 가장 먼저 나간다.

데이터들을 차례로 넣어주면서
스택 가장 위에 위치한 데이터, 즉 가장 나중에 들어온 데이터가
현재 데이터보다 작으면 스택에서 삭제해준다.
그리고 k를 감소시켜준다.

처음에 최중 숫자 길이를 변수로 설정해줬는데
그 이유는 위의 조건들은 숫자가 모두 같을 때에는
삭제 되지 않고 모두 스택에 들어가게 된다.
예) number = 10000, k = 2, result = 100

이 경우를 처리하기 위해서 애초에 최종 숫자 길이를 얻어
마지막에 최종 숫자 길이만큼 스택을 출력하여 반환했다.

TMI

문제 풀면서 노트를 3쪽이나..

1일 1알고리즘 완료🤓

참고

• 탐욕(그리디) 알고리즘(greedy algorithm)