✔Algorithm/programmers/2017팁스다운/level2/짝지어 제거하기 (with python)
5564 단어 알고리즘 문제programmers스택programmers
📖 문제
📝 풀이 과정1(효율성 x)
모든 문자열을 검사하는 직관적인 방식으로 문제를 풀었다.
- 문자열 내에서 2개 붙어있는 알파벳을 찾아서 ''(빈 문자열)로 대체한다.
- while문 밖으로 나왔을 때 만약 s가 빈 문자열이면 짝지어 제거하기가 성공적으로 이루어진 것이다.
- while문 밖으로 나왔을 때 s가 빈 문자열이 아니면 짝지어 제거하기가 실패한 것이다.
⌨ 코드1(틀린 코드)
- 시간 복잡도가 O(n^2)라서 효율성 테스트에서 통과하지 못했다.
예) s가 'ababaababa'라 하면, 2개 붙어있는 알파벳을 찾는데 for문을 n/2번 돌고, 총 n/2개의 짝을 지워야하기 때문에 O(n/2 * n/2) = O(n^2)
def solution(s):
# i는 문자열 index iterator
i = 0
while i < len(s)-1:
if s[i] == s[i+1]:
s = s.replace(s[i:i+2], '')
i = 0
else:
# 다음 인덱스 검사
i += 1
if len(s) == 0:
return 1
else:
return 0
📝 풀이 과정2
- 스택을 사용한다. ('질문하기'에서 발견한 풀이방법🥺)
- 문자열에 있는 문자들을 하나씩 순회한다.
- 만약 stack이 비어있다면 현재 문자를 stack에 push,
stack이 비어있지 않다면 현재 문자와 stack top을 비교한다.
- 현재 문자와 stack top에 있는 문자가 같다면 알파벳이 연속됨을 의미하므로 stack top을 pop한다.
같지 않다면 stack에 현재 문자를 push
- stack에 문자가 남아있는지 검사한다.
- stack이 비어있다면 짝지어 제거하기 성공
비어있지 않다면 짝지어 제거하기 실패
⌨ 코드2
from collections import deque
def solution(s):
stack = deque()
for i in s:
# stack이 비어있을 경우
if not stack:
stack.append(i)
# stack이 비어있지 않고, stack top이 현재 문자 i와 같다면
elif stack[-1]==i:
stack.pop()
# stack이 비어있지 않고, stack top이 현재 문자 i와 같지 않다면
else:
stack.append(i)
if stack:
return 0
else:
return 1
Author And Source
이 문제에 관하여(✔Algorithm/programmers/2017팁스다운/level2/짝지어 제거하기 (with python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@yellowsummer/Algorithmprogrammers2017팁스다운level2짝지어-제거하기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
모든 문자열을 검사하는 직관적인 방식으로 문제를 풀었다.
- 시간 복잡도가 O(n^2)라서 효율성 테스트에서 통과하지 못했다.
예) s가 'ababaababa'라 하면, 2개 붙어있는 알파벳을 찾는데 for문을 n/2번 돌고, 총 n/2개의 짝을 지워야하기 때문에 O(n/2 * n/2) = O(n^2)
def solution(s):
# i는 문자열 index iterator
i = 0
while i < len(s)-1:
if s[i] == s[i+1]:
s = s.replace(s[i:i+2], '')
i = 0
else:
# 다음 인덱스 검사
i += 1
if len(s) == 0:
return 1
else:
return 0
📝 풀이 과정2
- 스택을 사용한다. ('질문하기'에서 발견한 풀이방법🥺)
- 문자열에 있는 문자들을 하나씩 순회한다.
- 만약 stack이 비어있다면 현재 문자를 stack에 push,
stack이 비어있지 않다면 현재 문자와 stack top을 비교한다.
- 현재 문자와 stack top에 있는 문자가 같다면 알파벳이 연속됨을 의미하므로 stack top을 pop한다.
같지 않다면 stack에 현재 문자를 push
- stack에 문자가 남아있는지 검사한다.
- stack이 비어있다면 짝지어 제거하기 성공
비어있지 않다면 짝지어 제거하기 실패
⌨ 코드2
from collections import deque
def solution(s):
stack = deque()
for i in s:
# stack이 비어있을 경우
if not stack:
stack.append(i)
# stack이 비어있지 않고, stack top이 현재 문자 i와 같다면
elif stack[-1]==i:
stack.pop()
# stack이 비어있지 않고, stack top이 현재 문자 i와 같지 않다면
else:
stack.append(i)
if stack:
return 0
else:
return 1
Author And Source
이 문제에 관하여(✔Algorithm/programmers/2017팁스다운/level2/짝지어 제거하기 (with python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@yellowsummer/Algorithmprogrammers2017팁스다운level2짝지어-제거하기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- 만약 stack이 비어있다면 현재 문자를 stack에 push,
stack이 비어있지 않다면 현재 문자와 stack top을 비교한다. - 현재 문자와 stack top에 있는 문자가 같다면 알파벳이 연속됨을 의미하므로 stack top을 pop한다.
같지 않다면 stack에 현재 문자를 push
- stack이 비어있다면 짝지어 제거하기 성공
비어있지 않다면 짝지어 제거하기 실패
from collections import deque
def solution(s):
stack = deque()
for i in s:
# stack이 비어있을 경우
if not stack:
stack.append(i)
# stack이 비어있지 않고, stack top이 현재 문자 i와 같다면
elif stack[-1]==i:
stack.pop()
# stack이 비어있지 않고, stack top이 현재 문자 i와 같지 않다면
else:
stack.append(i)
if stack:
return 0
else:
return 1
Author And Source
이 문제에 관하여(✔Algorithm/programmers/2017팁스다운/level2/짝지어 제거하기 (with python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yellowsummer/Algorithmprogrammers2017팁스다운level2짝지어-제거하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)