큰 수 만들기
문제 링크
https://programmers.co.kr/learn/courses/30/lessons/42883
문제 풀이
각 변수 의미
- x : number 중 선택해야 하는 갯수 (ex. 길이가 8인 number에서 2개를 제거해야한다면 5개를 선택해야한다.)
- start : 탐색을 시작하는 위치
- end : 탐색을 끝내는 위치
- ans : number 중 가장 큰 값을 찾기 위해 비교 변수
- idx : 탐색하는 위치 중 가장 큰 값을 가진 자리의 index
풀이 과정
- k개 제거가 아닌 x 개를 선택하는 것으로 생각
- Greedy로 무조건 가장 큰 값들이 앞에 왔을 경우가 큰 값을 갖는다.
- 탐색을 한번 돌릴때 number 중 가장 큰 값 ‘한개’만 선택해서 answer에 더해준다.
- 따라서, 5개를 선택하는 경우라 할때 number의 길이가 8 이면 0의 index 부터 3 index까지 탐색을 한다. 왜냐하면 무조건 5개를 선택해야하기 때문에 ..!
- 만약 start와 end 값의 차이가 1인 경우 나머지를 다 그냥 answer에 더해준다. 제거를 이미 다해버려서 더 이상 제거를 할게 없는 상태이기 때문이다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def solution(number, k):
answer = ''
x = len(number)-k #x개 선택
start = 0
end = len(number) -x + 1
while len(answer) != x:
ans = -1
if end - start == 1:
answer += number[start:]
break
for i in range(start,end):
if int(number[i]) == 9:
idx = i
break
if int(number[i]) > ans:
ans = int(number[i])
idx = i
answer += number[idx]
start = idx+1
end += 1
return answer