Python Algorithm) Stack을 이용한 알고리즘 문제

1) 가장 큰 수 

선생님은 현수에게 숫자 하나를 주고, 해당 숫자의 자릿수들 중 m개의 숫자를 제거하

여 가장 큰 수를 만들라고 했습니다. 여러분이 현수를 도와주세요.(단 숫자의 순서는

유지해야 합니다)

만약 5276823 이 주어지고 3개의 자릿수를 제거한다면

7823이 가장 큰 숫자가 됩니다.

▣ 입력설명

첫째 줄에 숫자(길이는 1000을 넘지 않습니다)와 제가해야할 자릿수의 개수가 주어집니다.

▣ 출력설명

가장 큰 수를 출력합니다.

▣ 입력예제 1

5276823 3

▣ 출력예제 1

7823

 

코드)

num, m = map(int, input().split())
num = list(map(int, str(num))) #각 자리수에 있는 숫자 하나하나에 접근 할 수 있기 때문
# print(num)

stack = []
for currNum in num: #각 숫자를 돌면서
  #pop한다 언제까지? 
  #stack에 pop할 게 남아있고, 삭제해야만 하는 개수 m이 아직 남아있고, stack의 top이 나보자 작으면
  while stack and m>0 and stack[-1]<currNum:
    stack.pop()
    m -= 1 #하나 pop했으니까 삭제해야만 하는 개수도 하나 줄여준다. 
  #이후 빠져나오면 나를 push한다. 
  stack.append(currNum) #python에서는 push가 아닌 append사용

#그런데 이 경우 내 앞의 숫자들이 다 나보다 커서 더이상 pop이 일어ㅏ지 않고 push 만 되어서
# 삭제해야만 하는 개수 m이 아직 남아있는 경우가 있다. 
# 이 경우 어짜피 stack에 들어있는 수는 내림차순으로 들어있기 때문에 m개만큼 뒤를 잘라주면 된다. 
if m!=0:
  stack = stack[:-m]
#이제 list형식의 stack에 들어있는 각 숫자를 하나의 문자열로 붙여주면 답 완료
result = ''.join(map(str, stack))
print(result)#정답

※ Python에서 stack을 구현할 때 push가 아니라 append이다!

참고: 파이썬 스택은 push대신 append?

 

2) 쇠막대기

여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에

서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레

이저의 배치는 다음 조건을 만족한다.

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에

놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.

• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.

• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.

아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고,

점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.

이러한

stack의 top을 검사하는 것으로 충분하지 않고, 내 앞에 뭐가 있는지를 검사해야 할 때, 기존에 입력되었던 정보(여기선 괄호 문자열)에서 인덱스를 통해 검사하면 된다. 

이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할

수 있다.

1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반

드시 레이저를 표현한다.

2. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.

위 예의 괄호 표현은 그림 위에 주어져 있다.

쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의

쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은

총 17개의 조각으로 잘려진다.

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총

개수를 구하는 프로그램을 작성하시오.

▣ 입력설명

한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의

개수는 최대 100,000이다.

▣ 출력설명

잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.

▣ 입력예제 1

()(((()())(())()))(())

▣ 출력예제 1

17

 

코드)

# 해당 괄호가 쇠막대기의 시작, 끝 점인지, 레이저인지 구분은 그 다음에 뭐가 나오는지를 봐야한다. 
# ) 앞에 바로  (가 있었다면 이건 레이저
# ) 뒤에 바로 (가 아니라면 이건 쇠막대기의 시작
# 이 때 나는 stack에서 (을 )가 나오면 계속 pop해버리면서 남아있는 (개수를 세는 것으로 잘라지는 쇠막대기 개수를 더하는ㄴ 것 까지는 알겠는데
# 이 앞에 어떤게 있었는지를 어떻게 기억하는지가 궁금했음
# 그래서 stack과 기존 괄호 문자열을 두개 다 보면서 하는게 중요.
# 기존 괄호문자열에서 curr괄호 앞이 (였는지, )였는지를 검사해야한다.
str = input()
stack = []
result = 0
for idx, i in enumerate(str):
  if i == '(': #내가 '('이면 stack에 넣기
    stack.append(i)
  else: #내가 ')'이면 일단 하나는 pop (왜냐면 내가 레이저였어도 레이저의 '('는 이제 필요 없고, 내가 쇠막대기였어도, 쇠막대기가 끝났으니까 쇠막대기의 시작인 '('가 없어져야 하므로)
    stack.pop()
    if str[idx-1] == '(': #근데 내 바로 앞이 '('였으면 나는 레이저였음 => 즉 나로 인해 stack에 있는 쇠막대기들이 모두 잘려서 더해짐
      result += len(stack)
    else: # 내 바로 앞이 ')' 였으면 나는 레이저가 아님 즉, 난 쇠막대기였고, 이제 끝났음 => 내 마지막 조각 1개가 더해짐
      result += 1

print(result)

 

3) 후위표기식 만들기

중위표기식이 입력되면 후위표기식으로 변환하는 프로그램을 작성하세요.

중위표기식은 우리가 흔히 쓰은 표현식입니다. 즉 3+5 와 같이 연산자가 피연산자 사이에 있

으면 중위표기식입니다.

후위표기식은 35+ 와 같이 연산자가 피연산자 뒤에 있는 표기식입니다.

예를 들어 중위표기식이 3+5*2 를 후위표기식으로 표현하면 352*+ 로 표현됩니다.

만약 다음과 같이 연산 최우선인 괄호가 표현된 식이라면

(3+5)*2 이면 35+2* 로 바꾸어야 합니다.

※후위 표기식이 이해가 안되면 구글링으로 공부해보는 것도 좋습니다.

▣ 입력설명

첫 줄에 중위표기식이 주어진다. 길이는 100을 넘지 않는다.

식은 1~9의 숫자와 +, -, *, /, (, ) 연산자로만 이루어진다.

▣ 출력설명

후위표기식을 출력한다.

▣ 입력예제 1

3+5*2/(7-2)

▣ 출력예제 1

352*72-/+

 

코드) 

str = input()
stack = []
res = '' #python에서 문자열은 +로 연결 할 수 있음

#숫자는 그냥 바로
#연산자의 경우 그 연산자보다 우선순위가 높거나 같으면 pop
#                             아니면 stop 하고 append

for i in str:
  if i == '(':
    stack.append(i)
  elif i == ')':
    while stack and stack[-1]!='(' :
      res += stack.pop()
    stack.pop()
  elif i=='*' or i=='/':
    while stack and (stack[-1]=='*'or stack[-1]=='/'):
      res += stack.pop()
    stack.append(i)
  elif i=='+' or i=='-':
    while stack and (stack[-1]=='+' or stack[-1]=='-' or stack[-1]=='*' or stack[-1]=='/'): #아니면 '(' 빼고 다니까, while stack and stack[-1]!='(': 로 해줘도 된다.
      res += stack.pop()
    stack.append(i)
  else: # 숫자인 경우
    res += i

# 그 다음에 str이 끝났을 때 stack에 남아있는 연산도 다 출력
while stack:
  res += stack.pop()

print(res)

 

4) 후위식 연산

후위연산식이 주어지면 연산한 결과를 출력하는 프로그램을 작성하세요.

만약 3*(5+2)-9 을 후위연산식으로 표현하면 352+*9- 로 표현되며 그 결과는 21입니다.

▣ 입력설명

첫 줄에 후위연산식이 주어집니다. 연산식의 길이는 50을 넘지 않습니다.

식은 1~9의 숫자와 +, -, *, /, (, ) 연산자로만 이루어진다.

▣ 출력설명

연산한 결과를 출력합니다.

▣ 입력예제 1

352+*9-

▣ 출력예제 1

12

 

코드)

str = input()

stack = []

for i in str:
  if i.isdigit(): #숫자
    stack.append(i)
  else:#연산자면 stack에서 계산할 숫자 2개 꺼내서 연산후 다시 push
    #이 때 주의할 것은 먼저 들어간 것이 앞에 있던 숫자라는 것! 
    # 5-2 와 2-5는 다르다!
    # 5/2 와 2/5는 다르다!
    num2 = int(stack.pop())
    num1 = int(stack.pop())
    if i == '+':
      stack.append(num1+num2)
    elif i == '-':
      stack.append(num1-num2)
    elif i == '*':
      stack.append(num1*num2)
    else:
      stack.append(num1/num2)

print(stack[-1])

※ python에서 문자(열)이 숫자인지 확인하는 메소드

isdigit() 

true/false를 return 한다. 

이 외에도 

isdecimal(), isalpha().. 등 문자열에서 해당 문자가 무엇인지 판단하는 메서드가 다양하다. 

참고) appia.tistory.com/178

 

※ 이 문제의 경우 연산자가 문자열로 주어지므로 이걸 연산자로 활용하기 위해서 그냥 다 if문을 사용해주었는데, 그 외에도 다양한 방법이 있다. 예를들어, 

OPERATORS = {'+': 'add', '-': 'sub', '*': 'mul', '/': 'div'}

def apply_operator(a, op, b):

    method = '__%s__' % OPERATORS[op]
    return getattr(b, method)(a)

apply_operator(1, '+', 2)

이런 식으로 활용할 수도 있겠다.

참고) bit.ly/2JLqrdR