코드숨 알고리즘 day02 스택
코드숨 알고리즘 for 코딩 테스트 - DAY1 : STACK
괄호
스택 문제중 대표적인 문제가 아닐까? 중요한 건 이 문제를 왜 스택으로 풀어야하는지 알아야 한다는 점이다. 문제를 풀 아이디어는 입력값을 하나씩 검사하면서 스택에 괄호가 ‘(‘ 이면 집어 넣는다. 스택에 괄호가 ‘)’ 라면 최근에 집어넣은 괄호가 ‘(‘ 이면 빼낸다. 최근에 집어넣은 괄호가 없거나 ‘)’라면 return “NO”
def isValidPS(parenthesis):
stack = []
for s in parenthesis:
if s == '(':
stack.append(s)
elif s == ')':
if len(stack) and stack[-1] == '(':
stack.pop()
else:
return "NO"
if len(stack) > 0:
return "NO"
return "YES"
여기서 문제가 더 심화가 된다면 괄호가 소괄호 한개만이 아니라 여러개가 나올 수 있다. ({[]}) 인 경우. 이 경우에는 어떤 전략을 세울 수 있을까?
각자의 짝꿍이 누구인지 판별까지 하면 된다!
def is_correct_budgets(budgets):
stack = []
open_budgets = '({['
close_budgets = ')}]'
for s in budgets:
if s in open_budgets:
stack.append(s)
elif s in close_budgets:
if len(stack) and stack[-1] == open_budgets[close_budgets.index(s)]:
stack.pop()
else:
return "NO"
if len(stack) > 0:
return "NO"
return "YES"
위의 풀이에서 달라진 것은 소괄호를 체크해주던 부분이 괄호들의 배열로 체크해주는 것으로 바뀐 점이다.
단어 뒤집기 2
이 문제는 무작정 단어를 뒤집는 것이 아니라 태그가 나올 경우는 그대로 문자열을 돌려줘야 하기 때문에 태그가 아닐 경우에 stack에 쌓아서 문자열을 뒤집고 태그일 경우 뒤집은 단어를 붙인뒤에 태그가 닫힐 때까지 그냥 문자열에 그대로 붙이는 방법으로 구현했다.
def reverseString(sentence):
stack = []
result = ''
flag = False
for s in sentence:
if s == '<':
result, stack = joinStack(result, stack, '')
flag = True
elif s == '>':
result += s
flag = False
continue
if flag:
result += s
elif s == ' ':
result, stack = joinStack(result, stack, ' ')
else:
stack.append(s)
result, stack = joinStack(result, stack, '')
return result
def joinStack(result, stack, blank):
stack.reverse()
result += ''.join(stack) + blank
stack = []
return result, stack
문자열 폭발
def solution(sentence, bomb):
stack = []
result = 'FRULA'
n = len(bomb)
for s in sentence:
stack.append(s)
if stack[-n:] == list(bomb):
del stack[-n:]
if len(stack):
result = ''.join(stack)
return result
이 문제는 하나씩 순차적으로 폭발시킬 문자열이면 삭제하는 방법을 처음 생각했지만 그럴 경우 시간초과가 난다.
스택에 문자열을 하나씩 넣으면서 마지막부터 bomb의 길이만큼의 문자열이 폭발시킬 문자열과 같다면 스택에서 삭제해버린다.
후기
알고리즘 회고는 푼 바로바로 써야되겠다. 나중에 쓰니 그때 무슨 생각으로 썼는지 기억이 안난다. 시간이 지난 뒤 쓰는 것도 또 다른 나은 방법이 없나? 고민하게되서 또 다른 장점이 있는거 같다. 스택과 큐는 정말 기본적인 알고리즘 자료구조인데 이것들을 어떻게 효율적으로 쓸 수 있을지 좀 더 연습을 해야겠다.