728x90
반응형
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.
개요
문제를 처음 봤을 때 Stack의 괄호 짝 맞추기가 생각났다. 풀이과정에서 문자열을 복사하는 방법도 생각해보고 hashmap도 사용해보는 게 어떨까 싶었지만 풀이 순서를 세우고 보니 Stack이 과정 적합한 자료구조라 판단했다.
Solve
class Stack:
def __init__(self):
self.stack = []
def push(self, value):
self.stack.append(value)
def pop(self):
self.stack.pop()
def top(self):
try:
return self.stack[-1]
except IndexError:
return None
def solution(s):
stack = Stack()
stack.push(s[0])
for ch in s[1::]:
if stack.top() != ch:
stack.push(ch)
else:
if stack.top() == ch:
stack.pop()
if len(stack.stack) == 0:
return 1
else:
return 0
문자열을 제거해나가는 핵심 로직을 다음과 같이 계획하고 풀어나갔다.
- Stack에 저장하기전 저장된 문자열이 존재하는지 체크
- 저장된 문자가 없다면 저장한다
- 저장된 문자가 있다면 기존에 저장된 문자를 제거한다.
- Stack에 문자가 남아있다면 0을 Stack에 문자가 없다면 1을 리턴한다.
효율성 부분을 보니 뭔가 간당간당하게 풀리지 않았나 싶은 생각이 든다. 다른 사람들은 어떻게 풀었는지 체크해보자.
728x90
반응형
'Algorithm > Programmers' 카테고리의 다른 글
[Programmers] 2020 카카오 인턴십 > 키패드 누르기 (0) | 2023.02.21 |
---|---|
[Programmers] 가장 가까운 같은 글자 (0) | 2023.02.16 |
[Programmers] 카펫 (0) | 2023.02.12 |
[Programmers] JadenCase 문자열 만들기 (0) | 2023.02.09 |
[Programmers] 다음 큰 숫자. (0) | 2023.01.15 |