코드숨 알고리즘 day04 문자열
코드숨 알고리즘 for 코딩 테스트 - DAY4 : 문자열
문자열은 정말 자주 출제되는 유형이다. 여러가지 방법으로 풀 수 있어서 다양한 방법으로 여러가지 문제를 많이 풀어야한다. 카카오, 네이버 등 코테에 반드시 나오는 문제이기도하다.
균형잡힌 세상
def isBalance(sentence):
# 여는 괄호 ( [ 가 들어오면 stack에 담는다.
# 짝이 안맞는 경우를 위해 닫는 경우는 비교를 따로 분류한다.
# 스택으로 모든 문자열을 보기보단, 정규식?
stack = []
for s in sentence:
if not stack and (s == ')' or s == ']'):
return False
if s == '(' or s == '[':
stack.append(s)
elif stack:
if (stack[-1] == '(' and s == ')') or stack[-1] == '[' and s == ']':
stack.pop()
elif (stack[-1] == '(' and s == ']') or stack[-1] == '[' and s == ')':
return False
if stack:
return False
return True
while True:
sentence = input()
if sentence == '.':
break
result = "yes" if isBalance(sentence) else "no"
print(result)
앞에 스택에서도 푼 문제인데, 지금 다시 보니 더 효율적으로 코드를 짤 수 있었겠다는 생각이 든다. 여는 괄호, 닫는 괄호를 따로 변수로 빼서 비교하면 보기에도 좋을거같다.
def isBalance(sentence):
stack = []
open_budgets = '(['
close_budgets = ')]'
for s in sentence:
if not stack and s in close_budgets:
return False
if s in open_budgets:
stack.append(s)
elif s in close_budgets:
if stack and stack[-1] == open_budgets[close_budgets.index(s)]:
stack.pop()
else:
return False
if stack:
return False
return True
리팩토링을 했다. 하드코딩 되어있던 부분들을 변수로 빼서 포함되어있는지 여부를 보고있게 변경하였다. 또 짝꿍 괄호의 인덱스를 활용해서 스택 마지막의 괄호가 자신의 짝이 맞는지 확인하도록 변경하였다. 미리 작성해두었던 테스트코드가 통과하는지 확인하면서 조금씩 변경하였다!
IOIOI
def solution(n, sentence):
# Pn는 I 와 O가 번갈아가면서
# 길이가 2n+1
pn = 'I' + 'OI' * n
count = 0
i = 1
while i < len(sentence) - 1:
if sentence[i:i + len(pn)] == pn:
count += 1
while sentence[i + len(pn): i + len(pn) + 2] == 'OI':
count += 1
i += 2
i += len(pn) - 1
i += 1
return count
문제를 보고 해결법은 금방 찾았으나 최적화하는데 오래걸렸다. 나정님의 도움으로 최적화를 할 수 있었다.
처음에는 단순하게 하나씩 확인하는 방법으로 구현을 했는데 시간이 오래걸렸다. 문제를 풀때 어떤 규칙성이 있는지 찾고 잔머리(?)를 잘 굴려야겠다.
최적화 방법은 IOI를 찾았을 때 그 다음 두 문자가 OI라면 앞서 발견한 IOI와 다른 IOI를 찾은것이기 때문에 OI가 이어지지 않을 때까지 count를 늘리고 인덱스도 2칸씩 이동한다. 이어지는 문자열이 종료되면 그 다음부터 다시 IOI 문자열을 찾으면된다.
AC
from collections import deque
def solution(functions, array):
"""
배열의 초기값과 수행할 함수가 주어졌을 때 각 함수를 수행 후 최종 결과를 리턴
R(뒤집기) : 배열에 있는 수의 순서를 뒤집는다.
=> R 생성 때마다 reverse하면 시간 초과
=> R이 짝수번 나오면 그대로이기 때문에 총 합이 홀수이면 뒤집는다.
D(버리기) : 첫 번째 수를 버리고 배열이 비어있으면 에러를 발생
=> R이 홀수 번일 때는 뒤집힌 것이기 때문에 pop
=> R이 짝수 번일 때는 원래로 돌아오기 때문에 popleft
:param functions: 수행할 함수 조합
:param array: 정수 배열 초기값
:return: 결과
"""
queue = deque()
for i in array:
queue.append(i)
cnt = 0
for f in functions:
if f == 'R':
cnt += 1
if f == 'D':
if queue:
if cnt % 2 == 0:
queue.popleft()
else:
queue.pop()
else:
return "error"
if cnt % 2 == 1:
queue.reverse()
return list(map(str, queue))
처음 해결방법은 역시 들어오는 함수마다 뒤집거나 버리기를 했었다. 하지만 그렇게 되면 R(뒤집기)가 들어올 때마다 정렬을 해줘야하기 때문에 시간이 오래걸린다.
따라서 R(뒤집기)는 마지막에 처리하는 걸로 빼버렸다. 뒤집기는 두번 뒤집으면 원래의 형태로 돌아오기 때문에 그에 맞춰 D도 앞에서 버릴지 뒤에서 버릴지 결정하게 만들었다.
여담으로 이 문제부터 테스트 코드를 다른 방식으로 짜보고 docString을 사용해보았다.
후기
문자열은 다양한 풀이법이 존재하기때문에 여러 문제들을 접해야한다. 주로 스택, 큐, 정렬, 이진탐색? 부분에서 자주 출제되는 것 같다. 문제를 해결하는 것은 어느 정도 구현할 수 있으나 역시 최적화가 문제다.