[level 2] 짝지어 제거하기

문제

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

제한사항

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

 

문제 풀이 접근법1

1) 만약 s의 길이가 1 이상이고, i가 s의 길이에서 -1을 한 것보다 작으면 s[i]와 s[i+1]을 비교한다.

2) 만약 s[i]와 s[i+1]이 같다면 s[i]를 공백으로 변환한다.(""이 되면 한칸씩 땡겨지므로 그 다음도 s[i])

3) i= 0으로 변경하여 다시 탐색할 수 있게 한다. 

4) 만약 s가 0이라면 문자열이 다 제거된 것이므로 break한다.

5) 만약 i가 len(s)-1과 같다면 문자열을 다 제거할 수 없는 것이므로 answer를 0으로 제거하고 break한다. 

6) 4, 5의 조건과 불일치하다면 i에 +1을 해서 탐색을 진행한다. 

def solution(s):
    answer = 1
    i = 0

    while True:

        if len(s) >1 and i < len(s)-1:
            if s[i] == s[i+1]:
                s = s.replace(s[i], "")
                s = s.replace(s[i], "")
                i = 0 

        if len(s) == 0:
                break

        if i >= len(s)-1:
            answer = 0
            break

        i+=1  

    return answer

테스트 케이스 1, 11, 16에서 런타임 에러

테스트 케이스 6, 7, 8, 10, 12에서 실패 했다.

효율성 테스트에서도 1(런타임 에러), 6, 7,8에서 실패했다. 

 

일단 코드 돌리고 나서 드는 생각이 스택으로 문제를 풀 수 있지 않을까? 였다. 

그래서 스택으로 문제를 다시 구현해보기로 함 

 

 

문제 풀이 접근법2

1)  check 리스트를 선언한다. 

2) 만약 check리스트의 길이가 0이라면 문자열 s의 현재 원소를 append한다.

3) 아니라면 check의 가장 꼭대기에 있는 문자(가장 최근에 append된 문자)가 현재 원소와 같은지 확인한다.

4) 만약 둘이 같다면 check.pop()으로 가장 꼭대기에 있는 문자를 빼낸다.

5) 둘이 같지 않다면 s[i]를check에 append한다. 

6) 만약 check의 길이가 0보다 크다면 다 제거할 수 없는 것이므로 answer를 0으로 변경한다. 

def solution(s):
    answer = 1
    check = []

    for i in range(len(s)):

        if len(check) == 0:
            check.append(s[i])
        else:
            if check[len(check)-1] == s[i]:
                check.pop()
            else:
                check.append(s[i])

    if len(check) > 0:
        answer = 0
    return answer

 

 

가장 기쁜건...나의 최대 약점 중 하나인(너무 많아서 사실 셀 수 없음..ㅎ)

스택문제를 온전하게 내 생각으로 풀었다는거!!!

이렇게 성장...하는건가요?

암튼 아주 뿌듯하도다 하하