Algorithm - 가장 큰 수 찾기(스택)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[가장 큰 수 찾기(스택)]

 

선생님은 현수에게 숫자 하나를 주고, 해당 숫자의 자릿수들 중 m개의 숫자를 제거하여 가장 큰 수를 만들라고 했다.

(단, 숫자의 순서는 유지해야 함)

 

만약, 5276823이 주어지면 3개의 자리수를 제거하여 7823이 가장 큰 숫자가 된다.

위의 조건을 모두 충족시키는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째 줄에 숫자(길이는 1000을 넘지 않음)와 제거해야 할 자리수의 개수가 주어진다.

 

*출력 설명

가장 큰 수를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys 
sys.stdin = open('AA/input_32.txt', 'rt')

num, m = map(int, input().split())
num = list(map(int, str(num)))

stack = []
for x in num:
    while stack and m > 0 and stack[-1] < x:
        stack.pop()
        m -= 1
    stack.append(x)
if m != 0:
    stack = stack[:-m]
res = ''.join(map(str, stack))
print(res)

# 출력 : 99776

 

input_32.txt(입력)

9977252641 5

 

 

중요내용

1. 스택(Stack) 자료구조는 라스트인, 퍼스트아웃의 방식(마지막으로 들어간 것이 가장 먼저 나오는 방식)을 가진다.
2. 파이썬에서는 리스트 자료형에서 append() 함수와 pop() 함수를 사용하여 스택 자료구조의 매커니즘을 구현할 수 있다.
3. 즉, append() 함수와 pop() 함수를 사용하여 리스트 자료형의 맨 마지막 데이터를 빼거나 추가하는 방식이다.
4. num = list(map(int, str(num)))은 변수 num에 들어온 숫자형 데이터를 문자열 자료형으로 바꾸고, 해당 문자열의 각 자리수를 숫자형 데이터로 리스트에 (하나씩)넣어주는 코드이다.
5. while 문의 조건 stack and m > 0 and stack[-1] < x는 리스트 stack에 데이터가 존재하고, m(제거 횟수)이 0보다 크며, 리스트 stack에 가장 마지막으로 들어간 데이터가 x보다 작다는 의미이다. (3가지가 모두 만족해야 반복문이 계속 실행됨)
6. stack[:-m]은 리스트의 마지막 m개 데이터를 잘라내는 슬라이싱 기능이다. (첫 번째 데이터부터 인덱스 번호가 -m인 데이터 바로 앞까지만 반환하겠다는 의미)
7. join() 함수를 통해 리스트의 각 데이터를 하나의 숫자로 만들 수 있다. (ex. res = ''.join(map(str, stack)))