[프로그래머스/PYTHON] 짝지어 제거하기

프로그래머스 '짝지어 제거하기'입니다.

 

문제 링크

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

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

---

● 문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

문제 설명

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

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

b aa baa → bb aa → aa →

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

제한사항

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

---

● 문제 해결 방향

정확성  측면에서 엄청 까다로운 문제는 아니라는 생각이 들었습니다.

순서대로 문자를 확인하면서 연속을 존재하는 알파벳을 제거해주면서 해결하면 됩니다.

 

저는 제일 처음에 while 반복문과 인덱싱을 활용해 정확성 부분은 모두 해결했지만

효율성 부분에서는 전부 실패했습니다.

 

고민끝에 Stack을 사용하여 푸는 방법을 선택했습니다.

---

● 문제 해결 코드

def solution(s):
    
    ns = [s[0]]
    
    for i in s[1:]:
        if len(ns) > 0 and ns[-1] == i:
            ns.pop()
        else :
            ns.append(i)
            
    return 0 if len(ns) else 1

문자열에서 문자를 하나씩 가져오면서

이전에 가져온 문자와 비교하여 같은 문자면 두 문자를 배열에 추가하지 않고

다를 경우에만 추가해 주었습니다.

 

모든 연속 글자를 제거하고 길이로 성공 가능 여부를 판단했습니다.

---

● 알게 된 것

1. 알고리즘을 먼저 생각하려고 하자
2. 문자열을 슬라이싱, 인덱싱 하는 것보다 배열을 사용하는 것이 더 낫다 ( 맞나..? )