프로그래머스 - 짝지어 제거하기

Programmers - 짝지어 제거하기

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

---

문제

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

 

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

b aa baa → bb aa → aa →

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

 

제한사항

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

문제 풀이

문자열의 길이가 최대 1,000,000이기 때문에 O(n^2)으로는 풀이할 수 없는 문제이다. 꼭 이렇게 생각하지 않더라도 이 문제는 흔한 스택(Stack) 사용 문제이기 때문에 스택을 사용하여서 유명한 "괄호 제거" 문제처럼 풀어 주었다.

 

풀이법은 간단한다. 문자들을 순회하면서 스택에 push해준다. 하지만 만약 이때 push 하고자 하는 요소가 stack의 최상위, 즉 top에 존재한다면 "짝지어 제거할 수 있는" 경우이기 때문에 push하지 않고 이미 들어있는 stack의 top을 pop 해준다. 그리고 이와 같은 행위를 반복적으로 수행해준 후, 만약 stack이 비어있다면(모두 짝지어 제거된 경우) 1을, 그렇지 않은 경우라면 0을 출력해주면 된다.

 

보통은 python으로 문제를 풀이하는데, 최근 프론트엔드 직군에서는 코딩 테스트에 사용할 수 있는 언어를 JavaScript로 제한하는 경우가 종종 있다고 하여 JavaScript로도 문제를 풀어보았다.

def solution(s):
    st = []
    
    for ch in s:
        if st and ch == st[-1]:
            st.pop()
            continue
        
        st.append(ch)
    
    return 0 if st else 1

function solution(s){
    const stack = [];
    
    [...s].forEach(x => {
        stack.length > 0 && x === stack[stack.length-1]
            ? stack.pop()
            : stack.push(x);
    });
    
    return stack.length ? 0 : 1;
}

JavaScript 코드에서 forEach를 사용했음에도 불구하고 Python이 더 느린 것을 보고 Python이 좀... 많이 느리다는 것을 깨달았다. 그런데 Python을 허용하는 코딩 테스트라면 Python의 실행 속도를 고려해 추가 시간(?)을 주는 것으로 알고 있어 큰 문제는 없다고 생각한다.

Python 결과

JavaScript 결과