2017_탑스다운_#1. 짝지어 제거하기

코딩테스트 연습 - 짝지어 제거하기 | 프로그래머스 (programmers.co.kr)

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

짝지어 제거하기

문제 설명

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

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

b aa baa → bb aa → aa →

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

제한사항

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

---

입출력 예sresult

baabaa	1
cdcd	0

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.
입출력 예 #2
문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.

---

( 문제 해결 설명 )

보기 처럼 baabaa가 주어지면

굵게 표시한 부분을 차례 차례 삭제 할 수 있다.

bbaa => aa

가능하므로 1을 리턴

 

예시2는 cdcd 불가능한 상황이다, 그러므로 불가능 0을 리턴

이럴때 문제를 어떻게 해결해야할까?

for문을 돌면서 순회하면서 확인해야 할까?

어거리로 구현할 수 있겠지만 문제가 발생할 경우가 너무많다.

예상되는 문제 => 시간초과, 여러개의 짝지어진 문자가 있을 때 무엇을 선택해야 다삭제 될 것인가? 하는 문제등이 있다.

 

그럼 for문을 돌면서 일일이 조건을 따지면서 문제를 푸는건 아닌거 같다? 그렇다면?

 

이문제의 원리를 이해하면 비교적 문제가 쉽게 풀립니다.

baabaa 이렇게 있는 문자열을 하나씩 꺼내 봅시다!

처음: b

aabaa   

보관함: b

다음: a

abaa 보관함:ba

다음: a

baa

보관함:baa  <= 짝지어지는 상황 발생!! ( + 짝지어 졌으니 제거합시다!)

보관함의 가장 최근값 [-1] 값과,

꺼낸 값이 같다면 삭제하면 되는것.

이것을 스택의 개념을 이용하면 술술 풀리는 것

그렇습니다 스택에 개념을 이용해서 문제를 풀면 문제를 쉽게 풀 수 있는 것 입니다.

이어서 해볼까요?

다음: b

aa

보관함: bb <= 또 발생

다음: a

a

보관함: a

마지막: a

( 모두 꺼냄 )

보관함: aa

 

이런 구현과정을 코드로 구현하면 문제를 쉽게 풀 수 있습니다.

 

---

[코드] 

def solution(s):
    if len(s) == 0:
        return 1

    news = []

    s = list(s)
    for i in range(0, len(s)):
        # 인덱스 에러 방지용
        if len(news) == 0:
            news.append(s[i])

        elif news[-1] == s[i]:
            news.pop()

        else:
            news.append(s[i])

    s = news
    if len(s) == 0:
        answer = 1
    else:
        answer = 0

    return answer

---

후기

 

어렵게 생각할 필요 없다!

simple is best!