프로그래머스 49일차 - 큰 수 만들기

 

해설

처음 위처럼 풀었다가 timeout error가 났다.

조합을 사용하므로 모든 조합을 고려해서 시간 초과가 났다.

[9, 4]
94
[4, 3, 3, 2]
23234
[8, 7, 7, 5, 4, 4]

 

그래서 이번에는 큰수들만 빼내서 k만큼 빼내니까 자리수가 이상하게 나오고 원하는 수가 안나왔다.

 

만약 이전 요소가 현재 요소보다 크다면
->result에 현재 요소를 저장하고
그렇지 않다면
이전 요소를 제거하고 현재 요소만 저장합니다.
제거한 뒤 리스트에 남은 그 이전 요소도 같은 방식으로 현재 요소와 비교합니다

위 방식을 안했기 때문인것 같다.

 

우선 입력을 리스트로 변환하고 result 리스트를 만들어 결과를 저장

 

입력받은 numbers를 하나씩 확인하면서 result리스트 맨 뒤에 추가합니다.

이때 현재의 numbers 요소와 그 이전 요소인 result 리스트 맨 뒤 요소의 대소를 비교합니다.

 

만약 이전 요소가 현재 요소보다 크다면 ->result에 현재 요소를 저장하고

그렇지 않다면 -> 이전 요소를 제거하고 현재 요소만 저장합니다.

 

제거한 뒤 리스트에 남은 그 이전 요소도 같은 방식으로 현재 요소와 비교합니다

k개의 수가 모두 제거 되었다면 더 이상 제거하는 작업은 하지 않고 그대로 요소를 저장합니다.

 

그리고 반복이 끝난 시점에서 아직 수가 k번 제거되지 않은 경우 결과의 맨 뒤부터 순서대로 제거합니다.

 

---

후 탐욕법 너무 어렵네... 정렬 + stack을 잘 이용하면 풀것 같은데 stack에서 자꾸 막혀버린다.

 

참고

https://happy-obok.tistory.com/15