[프로그래머스] 코딩테스트 연습 : 짝지어 제거하기 - PYTHON[파이썬]

https://programmers.co.kr/learn/courses/30/lessons/12973

코딩테스트 연습 - 짝지어 제거하기

 

---

⊙ 문제

⊙ 제한사항

⊙ 입출력 예

⊙ 입출력 예 설명

---

 

⊙ 문제 접근 과정

 

총 3번의 도전.

 

- 첫 번째 풀이 -

2중 반복문 + replace (일부 통과, 시간 초과)

def solution(s):    
    while len(s):
        flag = True
        for i in range(len(s)):
            if s[i]+s[i] in s:
                s = s.replace(s[i]+s[i],'')
                flag = False
                break
        if flag:
            return 0
    
    return 1

반복문을 돌려서 같은 것이 연달아 배열 안에 있다면 replace로 변경해주면 되겠다고 생각했어요.

 

문제점

1. 배열을 반복문 중 직접 건든다.

2. 2중 반복문으로 시간 복잡도(O(n^2))가.. (문자열이 1,000,000까지 인데...)

 

첫 번째 풀이 결론: 여러 허점이 많다.

 

---

 

- 두 번째 풀이 -

첫 번째 풀이 + set (일부 통과, 시간 초과)

def solution(s):    
    listS = set(list(s))
    
    for _ in range(len(s)//2+1):
        for l in listS:
            while l+l in s:
                s=s.replace(l+l,'')
    
    if len(s):
        return 0
    return 1

첫 번째 풀이 때의 replace 함수에 대한 미련을 버리지 못하고 한번 더 도전을 해보았어요.

이번에는 3중 반복문이네요.. ㅋㅋ

 

나름 반복을 줄인다고 set을 사용하고, 절반 길이를 사용해보았지만 역시나 근본적인 해결을 하지 못했습니다.

 

두 번째 풀이 결론: replace를 버리자.

 

---

 

- 마지막 풀이 -

stack (통과)

def solution(s):    
    stack = []
    
    for i in s:
        if not stack:
            stack.append(i)
            continue
        
        stack.pop() if stack[-1] == i else stack.append(i)
        
    if stack:
        return 0
    return 1

첫 번째 시도와 두 번째 시도에서 가장 큰 문제점은 n중 반복문과 배열을 직접 건든다였어요.

replace 함수를 사용하고 싶었나 봐요...

 

배열을 직접 건드리지 않고, 반복문을 한 번만 사용하여 해당 문제를 풀 수 있지 않을까?

고민하던 중 stack이 생각나더라고요.

 

바로 적용했습니다.

stack을 하나 생성해주고, 반복문을 돌려요.

 

stack에 값이 없으면,

현재 값을 stack에 넣어주고 다음으로 넘어갑니다.

 

stack에 값이 있으면,

최상단 값과 현재 값을 비교, 비교 후 같다면 pop, 다르다면 push

 

 

결론: 반복문이 끝까지 돌고 stack에 값이 남아있는지 없는지로 판별해주었더니 성공했어요.

---

⊙ 문제 풀이

 

def solution(s):    
    stack = []
    
    for i in s:
        if not stack:
            stack.append(i)
            continue
        
        stack.pop() if stack[-1] == i else stack.append(i)
        
    if stack:
        return 0
    return 1

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!