12973. 짝지어 제거하기 - stack

🔻 짝지어 제거하기

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

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

b aa baa → bb aa → aa →

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

입출력 예

s	result
baabaa	1
cdcd	0

👀
중꺽마... 5번 정도 풀고 통과한 코드.. 시간복잡도랑 메모리 제한도 잘 확인해야 함을 뼈저리게 느껴서 기록..

stack으로 풀 때는 pop, shift를 잘 활용하자!

[👩🏻‍💻내 코드]

시간초과 fail
while문을 사용하고, 값이 같은 경우엔 index를 계속해서 0으로 초기화해서 처음부터 다시 순환하는 코드이므로 작성하면서도 너무 비효율적이라고 생각했는데 역시나 시간초과가 떴다.

function solution(s) {
    let index = 0;
    let arrayS = [...s];
  	// index값이 s길이 초과하지 않고 배열에 값이 남아있을동안
    while (index < s.length && arrayS.length != 0) {
        // index를 하나씩 두고 비교
        if (arrayS[index] === arrayS[index + 1]) {
            // 같을 경우 배열에서 값 지우고             
            arrayS.splice(index,2);
            // index 처음부터 다시 돌도록
            index = 0;
        }
        // 같지 않으면 index 증가시키기
        else index += 1;
    }
    // 배열이 비어있는 경우 true
    return arrayS.length === 0 ? 1 : 0;
}
                                 

효율성 fail
stack을 떠올려서, 기존 배열에서 첫번째 값을 빼서 newS에 저장하고 newS의 마지막 값과 기존 배열의 첫번째 값을 비교하여, 같은 경우 기존배열.shift(), newS.pop()을 통해 값을 제거하였다. 다른 경우 newS에 값을 push하여 마지막에 newS에 값이 없다면 1을 반환하도록 풀었다.

하지만 효율성 test에서 처참히 실패.. for문에서의 i를 index로 어떻게 활용하면 좋을지 떠올리지 못했던 코드. 기존 배열에서 shift하여 temp에 저장하는 과정이 불필요한 코드이다.

function solution(s) {
    // 기존 배열에서 빼온 값을 저장할 stack 역할 배열
    let newS = [];
    let arrayS = [...s]
                           
    for (let i = 0; i < s.length; i++) {
  		// 기존 배열의 제일 앞에 값 
        let temp = arrayS.shift();
  		// stack이 비어있다면 값 넣기
        if (newS.length == 0) newS.push(temp);
  
  		// // stack의 가장 마지막 값과 기존 배열의 가장 앞에 값 비교
        else {
  			// 같다면 stack의 마지막 값 없애기
            if (newS.at(-1) === temp) newS.pop();
  			// 다르다면 stack에 값 추가
            else newS.push(temp);
        }
    }
    return newS.length === 0 ? 1 : 0;
}

통과!
굳이 기존 배열의 첫번째 값들을 삭제할 필요가 없기 때문에 바로 위 코드에서 shift하여 비교 후 저장하거나 삭제하는 불필요한 과정을 제거하였다. for문의 초기문의 변수를 index에 활용하여 접근하였고 결과는 통과!

function solution(s) {
    let splited = [...s];
    const stack = [];
    
    for (let i = 0; i < s.length; i++) {
        // stack이 비어있거나, 기존 배열의 값과 같지 않다면
        if (stack.length === 0 || stack.at(-1) != splited[i]) {
            // stack에 값 추가
            stack.push(splited[i]);
        }
        // 같다면 stack의 마지막 값 제거
        else stack.pop();
    }
    return stack.length === 0? 1 : 0;
}