스택을 사용하는 문제

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

 

정리하면 2개가 붙있는지 확인 후 제거하고 제거한 문자열을 다시 붙여서 위 과정 반복

일단 앞에 인덱스를 확인해서 같으면 제거 
3개가 붙어있다면 두개만 제거해야하나?
제거 후 반복은 어떻게?

 

3개가 연속되어도  2개만 제거하는 게 맞았다

제거 후 반복은 처음엔 재귀함수로로 했다

 

function solution(s) {
    let str = ""
    for (i = 0; i < s.length; i++) {
        if (s[i] === s[i + 1]) {
            i++
            continue
        } else { str += s[i] }
    }
    if (str.length === 0) {
        return 1
    } else if (str.length === s.length) {
        return 0
    }
    return solution(str)
}

당연히 결과는 좋지 못했다. 시간도 굉장히 오래 걸리고 비효율적인 방법이다.  다음에 시도한 것은 재귀 부분을 반복문으로 처리 하는 것이었는데 이것도 이중 반복문이 되어서 좋지 못했다. 

 

그래서 다른 사람들의 답을 보고 코드를 뜯어보기로 했다. 

function solution(s) {
    if (s.length % 2 != 0) return 0; 
    
    const stack = [];
    for (let i = 0; i < s.length; i++) { 
        if(stack[stack.length - 1] === s[i]) {
            stack.pop();
        } else {
            stack.push(s[i]);
        }
    }
    return !stack.length ? 1 : 0;
}

예시)"baabaa"
b
0 푸쉬 [ 'b' ]
a
1 푸쉬 [ 'b', 'a' ]
a
2 팝 [ 'b' ]
b
3 팝 []
a
4 푸쉬 [ 'a' ]
a
5 팝 []

아주 간단해 보인다. 그런데 어딘가 익숙한 모습이다. 자료 구조 중 스택을 이용해서 푸는 문제라고 한다. 새로 들어온 데이터가 바로 바로 밑에 데이터랑 같으면 날려버리고 다르면 추가하는 방법이다. 이게 코드로만 보면 잘 이해가 되지 않아서 찍어봤다.  이해하는데 도움이 많이 되었고 스택이란 구조를 찾아만 봤지 이렇게 사용할 수 있구나 하는 것을 처음 알게 되었다.

 

자료 구조에 대해서 일단 찾아보긴 하는데 이걸 어떻게 쓰는거야 했는데 필요에 따라 스택이란 구조를 사용하니 반복을 한 번만 하면 되어 시간이 확 줄어든다. 그리고  함수가 실행되면 가장 먼저 if (s.length % 2 != 0) return 0;  이렇게 홀수인지 판별해서 리턴을 하는데 이것도 별 거 아닌 거 같지만 문제의 핵심을 찌르는 부분인 것 같았다. 저 한 줄로 인해서 모든 홀수 길이의 문자열은 검사를 안해도 되니까 성능적으로 큰 향상을 기대할 수 있다.