[프로그래머스] '짝지어 제거하기' 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]
   
   [Most 1 의 풀이]

---

 

문제 설명

 

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

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

b aa baa → bb aa → aa →

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

 

 

 

제한사항

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

 

 

 

입출력 예

s	result
baabaa	1
cdcd	0

알고리즘 분석

 어려운 문제는 아니다. 효율성 검사와 시간초과만 없었다면...

 

내 코드는 문제를 통과하지 못했다. 결과가 잘못나온 것은 아니다. 그저 시간이 오래 걸릴뿐.. 

그래서 다른 코드를 참고했다. 

 

• 나의 풀이

def solution(s):
    s_cp = ''
    t_f = True
    while t_f:
        t_f = False
        if not s: return 1 
        for str_ in range(1,len(s)): 
            if s[str_-1] == s[str_]: 
                s = s[:str_-1] + s[str_+1:]
                t_f = True
                break
    return 0 

 내 코드는 인덱스 1부터 시작하는데, 그 이유는 현재 인덱스에서 -1한 인덱스와 비교하기 때문이다. 같은 문자열이라면 그 두문자를 제외한 문자를 s에 덮어쓴 뒤 다시한번 반복하는 코드이다. 만약 같은 문자가 하나도 없다면 반복문을 탈출하게 된다. 

 

• Most 1의 코드

def solution(s):
    answer = []
    for i in s:
        if not(answer): # answer가 빈 리스트라면
            answer.append(i) # i를 answer에 추가 
        else: # answer가 빈 리스트가 아니라면 
            if(answer[-1] == i): # answer의 맨 끝에 있는 요소가 i와 같다면
                answer.pop() # answer의 맨 끝의 값을 버린다. 
            else: # 다르다면
                answer.append(i) # i를 answer에 추가    
    return not(answer) # 빈 리스트라면 1, 아니라면 0을 반환

 

역시 좋아요를 제일 많이 받은 코드 답게 이해하기도 쉬우며 간단하다. 

주석 외에 별다른 설명은 필요없을 것 같다.