프로그래머스 LV2 큰 수 만들기

문제 알고리즘 유형 : Greedy 

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

1. 문제 풀이 : Stack 사용

: Greedy 알고리즘이란 미래의 일을 생각하지 않고 현재 가장 최선의 방식을 찾는 탐욕 알고리즘이라고도 불린다. 이 알고리즘에 대해 알아보다보니 Stack 을 사용해 반복문을 통해 현재 값 넣어주고 다음 값 혹은 이전 값과 비교해서 없애주는 형식으로 처리하면 될 것 같았다. 물론 이를 코드로 적용하기엔 많은 오류와 구글링이 있었다. 

 

2. 풀이 방식

1) 먼저 answer이라는 빈 리스트를 만들어주고 이 곳에  numbers로 입력받은 값 하나씩 넣어주고자 했다. 

 for문으로 반복을 통해 넣어주고자 했다. 

2)  입력받은 값 넣어줄 때 가장 큰 수가 맨 앞에 위치해야 하므로 이를 비교해주는 과정이 필요함을 느꼈다. 

3) answer에 값이 들어있고 제거되어야 할 k도 있을 때를 조건으로 가져왔다.

• answer 있던 값이 들어올 현재 값보다 크면 그냥 현재 값은 그대로 push 해주면 된다.
• answer 있던 값이 들어올 현재 값보다 작으면 이전 값은 삭제하고 하나 삭제했으므로 k도 -1 해준 뒤 현재 값 push 해준다. 

4) 반복문이 끝나고도 K가 남아있을 경우 

 ex) K=2 numbers = 999 일 때 

 k = 2 answer = [] 

 k = 2 answer = [9] 

k = 2 answer = [9,9]

k = 2 answer = [9,9,9] 

값은 9가 되어야 하므로 뒤에서부터 K 만큼 삭제해줘야 한다. 

 

3. 최종 코드 

최종 코드

4. 느낀 점 

: 시간복잡도는 number에 들어있는 값 만큼 반복하므로 O(N)을 따라갔을 것이다. 

: 스택을 사용할 것을 알고 있었지만 이를 코드로 구현하기 너무 힘들었다. 구체적으로 적기가 힘들었는데 많은 연습만이 답인 것 같다.

: 마지막 K만큼 뒤에서 빼주는 과정이 참신했고 간결하게 풀 수 있음을 깨달았다. 대단한 사람들이 참 많다.. 

: 아마 저번주에 푼 문제였지만 그 때 블로그 작성을 까먹고 지금 다시 보니 문제 이해가 좀 되는 것 같기도 하다. 꾸준한 반복이 답이다..