[프로그래머스] 코딩테스트 연습 - 짝지어 제거하기(Python)

코딩테스트 연습 - 짝지어 제거하기 [2017 팁스타운]

풀이 - Stack

문제를 처음 풀었을 때는 제한사항을 안보고 while문에 문자열 s를 변경하며 풀다보니 효율성에서 시간초과가 나왔습니다..ㅎㅎ 아무래도 문자열 s를 한번 보더라도 문자열 s의 길이가 길어지면 중간에 추가되는 문자열 생성이나 삭제같은 방법으로 문자열 s를 갱신하는 연산도 같이 많아져 시간초과가 발생한 것 같습니다.

 

예를 들어 보면 문자열 s의 길이가 10,000개이고 짝이되는 알파벳이 (0, 1)와 (2, 3)에 있다고 가정해보겠습니다.

   1. (0, 1)을 빼고 인덱스 2~99까지를 0~9,997로 복사

   2. (0, 1)[원래 (2, 3)인덱스]을 빼고 인덱스 2~9,995까지 복사

위와 같은 연산이 계속된다면 아무리 문자열을 한번 보더라도 갱신하는 연산이 훨씬 오래 걸리게 되겠죠?

 

그래서 문자열을 한번 보는 것과 동시에 문자열 갱신이 필요하지 않은 방법으로 stack을 사용하면 위의 예보다 연산이 굉장히 줄어 O(n)에 문제를 해결할 수 있어집니다.

 

Code

from collections import deque
def solution(s):
    answer, idx = 0, 0
    stack = deque(['-'])
    s += '-'		# s의 마지막 인덱스 확인을 위해 추가
    while idx < len(s)-1:
        if stack[-1] == s[idx]:     # stack과 비교하여 같으면 stack pop
            stack.pop()
        elif s[idx] == s[idx+1]:    # 알파벳이 연속된 경우
            idx += 1
        else:
            stack.append(s[idx])
        idx += 1
    if len(stack)==1:   # stack에 0만 있는 경우 정답
        answer = 1
    return answer

1. stack에 '-'(알파벳이 아닌 아무 문자)를 넣어 초기화합니다 (stack[-1]에서 index에러를 피하기 위해)

2. 문자열 s에 '-'를 이어붙입니다 (마지막 인덱스를 문자를 확인하기 위해 - 반례 s = "a", "abbaaa")

3. [while문] 조건에 맞게 stack과 idx를 조절합니다 (stack먼저 확인)

4. stack의 길이가 1('-' 초기화)이면 True 이므로 answer = 1

 

문제 설명

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

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

b aa baa → bb aa → aa →

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

 

제한사항

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

입출력 예

s	result
baabaa	1
cdcd	0