[Programmers] 짝지어 제거하기

sunriseGong·2021년 11월 12일
0

문제

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

문자열에서
같은 알파벳이 2개 붙어 있는 짝을 찾습니다.

그다음, 그 둘을 제거한 뒤,
앞뒤로 문자열을 이어 붙입니다.

이 과정을 반복해서
문자열을 모두 제거된다면 1을
그렇지 않다면 0을 반환하는 함수를 만드세요.

ex)
문자열 baabaa 라면

baabaa → bbaa → aa → 완전 제거 -> 1 리턴

문제열 cdcd 라면

같은 알파벳이 붙어있지 않으므로 제거 불가 -> 0 리턴


나의 풀이

재귀로 도전했는데
시간복잡도 때문인지 테스트의 절반가량 통과가 안된다;

function solution(s) {
    let arr = s.split('');
    
    const recur = (arr) => {
        let exArr = [...arr];
        
        for (let i = 0; i < arr.length; i++) {
            if (arr[i] === arr[i+1]) {
                arr.splice(i,2);
                break;
            }
        }
        
        if (arr.length === exArr.length) return
        
        recur(arr)
    }
    recur(arr);

    return arr.length === 0? 1 : 0
}

스택 방식으로 도전해 성공

function solution(s) {
    let stackArr = [];
    
    for (let i = 0; i < s.length; i++) {
        stackArr[stackArr.length -1] === s[i]? stackArr.pop() : stackArr.push(s[i])
    };
    return stackArr.length? 0 : 1
}

stackArr
스택을 구현할 배열을 생성

for문
문자열 s 를 순회하며
스택 배열의 마지막 요소와 비교해
동일하면 마지막 값을 지우고(pop)
다르다면 값을 추가(push) 해서
후입선출을 구현한다.

return
스택 배열의 길이가 0을 초과하면
짝지어 제거되지 못한 알파벳이 존해하는 것이므로 0을
스택 배열의 길이가 0과 같다면
모든 알파벳이 제거 되었으므로 1을 리턴한다.


시간복잡도 생각해보기

스택 풀이의 시간복잡도는
문자열의 길이만큼만 for문 한번 돌고 끝나므로
O(n) 이지 싶다.

재귀 풀이의 시간복잡도는
요소가 제거되지 않을 때까지
for문을 계속 돌기 때문에
시간복잡도 측면에서 좋지 않을 것 같다.

profile
심심해야 공부하게 된다.

0개의 댓글