728x90
반응형
문제:
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19,12,14,92,94,24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수를 매개변수로 주어집니다. number에서 k 개의 수를 제거 했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
풀이 과정:
단순히 number 중 작은 순으로 빼는 것이 아니라는 것을 마지막 예시 케이스 4177252841을 보면 알 수 있다. 따라서 이 문제는 탐욕법을 사용해서 풀어야 하는 문제이므로 문제 풀이를 생각하였다. 따라서 각 자리별로 한번씩 다 빼보아서(ex 1924의 경우 924, 124, 194, 192) 이 중 가장 큰 경우를 선택하도록 하였다. 대부분의 경우에 대해서 통과를 하지만 역시나 자릿수가 큰 경우에 시간초과가 발생하였다.
그래서 탐욕법이 아닌 다른 방법도 생각해보았는데 스택을 활용해서 푸는 것이 효율적으로 할 수 있었다.
숫자를 다음과 같은 규칙에 따라 스택을 쌓아가면 큰 수를 만들어 갈 수 있다.
1. 하나의 값을 넣는다
2. 맨 위에 쌓인 값과 그 바로 밑(맨 위에서 두번째 값)을 비교한다.
3. 맨 위의 값이 더 클 경우 두 개의 값의 자리를 바꾸고 pop 해내서 빼낸다. 맨 위의 값이 작으면 다음 단계로 넘어간다
4. 1~3을 k번 빼내거나, number를 다 쌓으면 끝낸다.
다음은 예시 케이스 4177252841을 쌓는 과정을 나타냈다.
|
|
|
|
|
|
|
|
|
|
1 |
|
4 |
비교 대상이 없어 통과한다. |
4 |
위 값이 작으므로 그냥 패스한다. |
|
|
|
|
|
|
7 |
|
|
|
|
|
1 |
7을 쌓았을 때 자리를 |
7 |
자리를 바꾼 후 1을 빼 |
|
이 역시 7이 더 크므로 |
4 |
바꾼다. |
4 |
고 다시 4와 비교를 함 |
7 |
자리를 바꾸고 4를 뺌 |
이 작업을 반복해서 하면 큰 수를 만들 수 있다.
하지만 54321, k=1 와 같은 경우에는 하나도 빠지는 것 없이 54321 순으로 쌓이게 된다. 이 규칙으로 쌓았을 때 마지막으로 갈 수록 수가 작아지므로 뒤에서 부터 잘라서 사용하도록 한다.
우선 number가 string이므로 이를 list로 쪼개 하나씩 넣을 수 있도록 만들었다. 그리고 첫 수는 항상 넣고 시작하였다. 하나씩 넣으면서 Tos(Top of stack) 즉 지금 맨 위에 쌓인 부분의 인덱스를 하나씩 늘렸다. while 문이 규칙의 2,3번을 반복하는 과정이다. correct라는 변수는 4177252841와 같은 경우에 7을 넣을 때 두 번 연속 빼야하는데 이와 같은 행위를 하기 위해서 넣은 변수이다.
그리고 맨마지막에 54321 과 같은 경우를 해결하기 위해 뒤에서 부터 자르도록 하였다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | def solution(number,k): number=list(number) answer=[number[0]] Tos=0 for i in range(1,len(number)): answer.append(number[i]) Tos+=1 correct=1 while (correct and k !=0): correct-=1 for j in range(Tos,len(answer)): if answer[j-1]>=answer[j]: pass else: answer[j-1],answer[j]=answer[j],answer[j-1] answer.pop() correct+=1 Tos-=1 k-=1 break answer="".join(answer) return answer[:len(answer)-k] | cs |
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [Programmers]Lv 2. 소수 찾기 (0) | 2019.02.14 |
|---|---|
| [Programmers]Lv 1. 체육복 (0) | 2019.02.13 |
| [Programmers]Lv 1. K번째수 (0) | 2019.02.11 |
| [Programmers]Lv 2.더 맵게 (0) | 2019.02.10 |
| [Programmers]Lv 1.같은 숫자는 싫어 (0) | 2019.02.09 |