Level 2. 큰 수 만들기

큰 수 만들기

코딩테스트 연습 > 탐욕법 > 큰 수 만들기

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

---

문제 설명

---

문제 구상

• 입력: 숫자로 이루어진 문자열, 문자열에서 원소를 제거할 횟수
• 과정:
  1. 빈 리스트를 만든 후, 해당 리스트에 다음과 같은 while반복문을 이용하여 필터링 된 원소를 append()한다.
  2. 리스트의 값이 존재하고, 리스트의 마지막 값이 while문에 들어온 원소값보다 작고, 원소를 제거할 횟수 K가 0보다 클 때,
     1) K -= 1를 이용하여 횟수가 차감됨을 표현한다.
     2) 리스트의 마지막 값을 pop한다.
  3. 리스트에 해당 큰 값을 append한다.
  4. ''.join()을 이용하여 문자열 형태로 변환한다.

---

문제 풀이

첫번째 시도: 시간초과

len(number)-K 의 가짓수만큼 combinations를 이용하여 list를 구성 한 뒤 max값을 return하는 방법을 구상했습니다..만 두개의 테스트케이스에서 시간초과가 발생했습니다.

# 1st trial : time over
# Input value
number = '1924'
k = 2

# Import module
from itertools import combinations

''.join(max(set(combinations(number,len(number)-k))))

두번째 시도: 시간초과

첫번째 시도에서 max(set())을 이용한 것이 문제였나 싶어 아래와 같이 설정했으나, 위의 과정과 유사하게 시간초과가 발생했습니다.

# 2nd trial : time over
# Input value
number = '1924'
k = 2

answer = '' # Set initial value
# Import module
from itertools import combinations

for c in list(combinations(number,len(number)-k)):
    if answer == '' or int(answer) < int(''.join(c)):
        answer = ''.join(c)
answer

세번째 시도

모듈을 사용하지않고 문제 구상에서 제안한 흐름에 맞추어 코드를 작성하였습니다.

# 3rd trial
# Input value
number = '1924'
k = 2

answer = [] # Set initial value
for n in number: # Consider numbers's elements
    while answer and answer[-1] < n and k > 0: # Use while when list answer != [] and answer[-1]'s value is smaller than n and number of K != 0
        k -= 1 # K -=1
        answer.pop() # pop value
    answer.append(n) # append value
''.join(answer) # Transform list to string