스택(stack) 자료형의 성질을 사용한 알고리즘 풀이를 알아보자.
스택이란?
스택은 영어로 쌓아놓은 더미 의 뜻을 가진다.
제일 밑에 있는 책은 가장 처음 쌓아진 책이다. 가장 위에 있는 책은 가장 나중에 올라간 책이다. 책을 가져올 때도 제일 위에 있는 책이 가장 먼저 가져와지고 제일 밑에있는 책은 모든 책이 사라진 후에 가져올 수 있다.
first in last out
먼저 들어오면 가장 나중에 나가는 것이 스택 자료형의 특징이다.
파이썬에는 스택 자료형이 존재하지 않기 때문에 리스트로 스택자료형을 구현해준다.
def make_big_num(nums, chance):
[1] num_list = list(map(int, str(nums)))
[2] stack = []
[3] for num in num_list:
[4] while stack and chance > 0 and stack[-1] < num:
[5] stack.pop()
[6] chance = chance - 1
[7] stack.append(num)
[8] if chance != 0:
[9] stack = stack[0:-chance]
[10]result_string = ''
for s in stack:
result_string = result_string + str(s)
return int(result_string)
print(make_big_num(9977252641, 5))[1] 우선 map함수를 통해서 들어온 숫자를 string으로 바꿔서 하나의 숫자에 접근할 수 있게 한다. 그리고 그 하나하나를 int로 바꾸고 리스트로 만든다. 결론적으로 int가 되지 않으면 숫자끼리 비교를 할 수 없다.
[2] 스택을 실현시켜 줄 빈 리스트를 정의한다. 이 리스트에 숫자가 0번인덱스부터 쌓일 것이다.
[3] 리스트 안의 value에 하나하나 접근한다.
[4] while문은 조건안에 들어있는 것이 참일 때 실행된다. 참이아니면 while문을 벗어난다. 여기서
- stack 이 존재할 때,
- chance(stack 리스트 안에서 내 앞에 있는 value를 제거할 수 있는 수 있는 횟수),
- stack 안에서 가장 마지막 숫자(가장 나중에 들어온 숫자, 지금 들어갈 숫자 바로 이전에 들어온 숫자)가 지금 들어갈 숫자보다 작을 때. 이 경우에 내 앞에있는 숫자를 제거하고 내가 들어가야한다.
위의 3가지 경우의 수가 모두 만족되면 while문이 실행된다.
그리고 [5] 에서 지금들어가야 하는 숫자(num)가 들어가기 전에 먼저 들어간 숫자가 num보다 작기 때문에(stack[-1] < num를 만족하기 때문에) stack안에서 가장 나중에 들어간 숫자를 빼준다(stack.pop()).
[6] pop()으로 가장 나중에 들어간 숫자를 제거했으니깐 제거할 수 있는 chance를 하나 감소시켜 준다.
- 예를들어 stack이 [3,4]이고 7이 들어가야 할 경우를 생각해보자.7은 바로 직전에 들어간 4보다도, 그 전에 들어간 3보다도 크다. 둘다 없애고 자기가 들어가야 하는 상황이다. 여기서 while문이 작동하여 4, 3을 차례로 pop()시키고 chance를 두번 감소시킨다. pop을 통해서 가장 나중에 들어온 value를 가장 먼저 끄집어내는 stack의 성질을 활용할 수 있다.
- 만약 stack이 [8,3,4]라고 가정해보자. 그리고 지금 stack에 추가되어야 할 num는 7이다. num는 자기보다 작은 4와 3을 pop을 통해서 제거할 것이다. 그리고 chance에 2개가 제거될 것이다. 8의 경우는 num보다 크다. 그래서 while문에서 이탈되어 바로 [7]이 실행된다.
[7] while문을 벗어나 추가해 주어야 할 num을 stack에 추가해준다. for문이 다 돌고도 chance가 0이 아니라면?
- 지금 까지 stack안에 차례로 value가 쌓였다는것은 존재하는 num_list에서 가장 큰수가 차례로 쌓였음을 보여준다. stack에 제일 마지막에 들어간 숫자를 지울 수 있는 chance가 존재함에도 불구하고 못지우는 경우가 발생할 수 있다. 만약 stack의 마지막에 들어간 숫자가 6이고, 앞으로 들어갈 숫자가 4와 3이면? chance를 사용할 수 없이 바로 stack에 append될 것이다.
그렇다면 남은 chance는 어떻게하는가?
다 써야한다. 다 써야하기 때문에 제일 뒤에 아무런 pop()옆이 들어간 4와 3을 남은 chance로 제거해주어야 한다.
[8] 이 실행된다. 그래서 chance가 남아있으면 [9]에서 남은 chance만큼의 인덱스는 제외 한 리스트를 가져온다.(남은 chance로 stack에서 제일 작은숫자들을 지우는 과정)
이제 stack에는 지울 수 있는 모든 chance를 활용하여 합치면 가장 큰 숫자가 되는 리스트가 담겨있다. 이제 이 리스트를 int로 만들어주어야한다.
[10]에서 리스트안의 숫자를 문자열로 바꿔서 빈문저열에 추가해주고 완성된 문자열을 int로 바꾸어 리턴한다.
