문제:

어떤 숫자에서 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



'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

+ Recent posts