📝 짝지어 제거하기

🖥 나의 JS 코드

첫번째 시도

처음에는 주어진 문자열을 조작하면서 while문을 순회하기 시작했는데테스트 코드는 모두 통과가 되었지만 효율성 검사에서 시간초과라는 에러를 발생시켰다.

function solution(s){

    let check_index = 0 ;

    while(check_index < s.length-1){
     // s 자체를 조작하면서 반복문 순회
        if(s[check_index] === s[check_index+1] ){
            s = s.slice(0, check_index) + s.slice(check_index+2, s.length);
            check_index = 0 ;
        } else{
            check_index += 1;
        }
    }
 // 남아있는 s가 있으면 0 없으면 1로 반환
    if(s.length === 0)
        return 1
    else
        return 0
}

이를 해결하기 위해 스택 2개 구현을 통해 반복문 조건을 바꿔보았지만 여전히 작동되지 않았다

function solution(s){

    let check_index = 0 ;
// 비교 스택, 문자열 스택을 생성 한뒤
  let stack = [], s_stack = s.split('');

    while(s_stack.length != 0){
// 비교 스택의 마지막 값과 문자열 스택의 처음 값을 비교하면서 스택 조작
        if(stack[stack.length-1] === s_stack[0]){
            stack.pop();
        } else {
            stack.push(s_stack[0]);
        }
            s_stack.shift();
        
    }
  // 비교스택에 원소가 아무것도 없으면 모두 제거된것
    if(stack.length ===0){
            return 1;
      
    }else {
        return 0;
    }
}

배열 2개를 반복해서 돌리는 것 자체가 크기에 의한 시간초과를 가져온다고 생각하여
스택 1개만을 사용하여 코드를 구현하였더니 해결이 되었다!!

따라서 최종 답안은 다음과 같다👇

function solution(s){

  // 답안 스택 
  let stack = [];

  // s의 길이 만큼 반복
    for(let i = 0 ; i < s.length ; i++){
	
      // 답안 스택의 마지막 원소가 비교할 문자열의 문자와 같으면 
      // 답안 스택의 마지막 원소를 제거
        if(stack[stack.length-1] === s.charAt(i)){
            stack.pop();
        } else {
          // 그게 아니라면 원소를 넣어줌
            stack.push(s.charAt(i));
        }
        
    }
    
  // 모든 반복문이 끝난후 스택에 아무런 원소가 존재하지 않으면
  // 모두 제거된 것이므로 1을 반환
    if(stack.length ===0)
        return 1;
    else 
        return 0;
}

두번째 시도

처음에 시도했을 때, 배열 두개를 여전히 사용하였으며 이는 역시 시간초과를 일으켰다
그래서 첫번째 시도했을때의 실수를 떠올려 배열을 한개만 사용하여 진행하였다

달랐던 부분은 checkStack에 값을 넣을때, charAt을 사용하지 않고 [ ] 값의 참조를 통하여 더 단순한 코드로 로직을 구현하였다

최종 코드는 다음과 같다👇

function solution(s) {
    const checkStack = [];
    // 주어진 문자열 길이동안 반복하면서
    //checkStack의 마지막 원소와 문자열 s[i]가 가리키는 문자가 같으면 스택에서 제거하고
    // 다르다면 스택에 넣어주기
    for (let i = 0; i < s.length; i++) {
        if (checkStack[checkStack.length - 1] === s[i]) {
            checkStack.pop();
        } else {
            checkStack.push(s[i]);
        }
    }
    // 스택의 첫번째, 두번째 원소가 같으면 문자열이 모두 제거 되지만,
    // 그게아니라면 짝지어 제거하기 실패
    if (checkStack[0] === checkStack[1]) {
        return 1;
    } else {
        return 0;
    }
}