알고리즘/프로그래머스

[프로그래머스] LEVEL2 - 짝지어 제거하기 (Python)

Coblin 2020. 10. 5. 18:58
반응형

 

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

 

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

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙

programmers.co.kr

문제설명

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

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

b aa baa → bb aa → aa →

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

제한조건

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

입출력 예

s result
baabaa 1
cdcd 0

입출력 예 설명

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

answer

def solution(s):
    temp = [] #비교를 하기위한 빈 배열을 만들어준다.
    for i in s:
        #temp가 비어있다면 i(문자)를 배열에 추가한다.
        if len(temp) == 0:
            temp.append(i)
        #temp의 마지막 문자가 i(문자)와 같다면 해당 문자를 빼준다.
        elif temp[-1] == i:
            temp.pop()
        #temp가 존재하지만 마지막문자가 i와 같지 않다면 i(문자)를 배열에 추가한다.
        else:
            temp.append(i)
    #for문이 다 돌고 배열이 비어있다면 문자열을 모두 제거할 수 있으므로 1을 반환
    if len(temp) == 0:
        return 1
    #배열이 비어있지 않으면 제거할 수 있는 문자열이 없기 때문에 0을 반환
    else:
        return 0

스택을 이용해야 한다는걸 모르고 이중for문을 돌리는 등 여러 삽질을 하다가 시간이 한참 지나고 나서야 스택을 이용해 풀면 된다는걸 깨달았다.

스택을 떠올리기전에는 그렇게 어려웠던 문제가 스택을 활용하니 바로 풀려버리니 허탈할 지경 ㅠㅠ

문제를 보고 어떤 것을 사용해야하는지 판단이 됐으면 좋겠지만 문제풀이 경험도 적고 자료구조 공부도 안해봤으니 매번 맨땅에 헤딩하는 기분이네요 공부 좀 빡세게 해야겠습니다!

반응형