프로그래머스 코딩테스트 풀이(js) > 짝지어 제거하기(lv2)

문제 🔽

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

프로그래머스

 

다른사람 풀이 🔽

function solution(s) {
    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;
}

내풀이🔽

1. 첫번째 시도 -> 실패 ❌ ( 추정 원인: 시간복잡도 최적화 실패 )

function solution(s)
{
    // 성공>return 1
    // 실패>return 0
    // 반복분 > 탐색하면서 > [n] =[n+1] 이면 바로 그 두개 삭제 > 그리고 다시 끝까지 탐색 >
    // 탐색이 끝났는데 > length 0이면 > return 1 아니면 return 0 
    
    if(s.length%2){
        return 0;
    }

    var answer = 0;
    let string = [...s]
    
    
    let indicator = true;
    if(string.length%2==1){
        return 0;
    }

    while(indicator){
        if(string.length==0){
            answer = 1;
            indicator=false;
            break;
        }
        for(let i=0; i<string.length; i++){
            if(i==string.length-1){
                answer = 0;
                indicator=false;
                break;  
            }else{
                if(string[i]===string[i+1]){
                    string.splice(i,2)
                    break;
                }
            }
        }
    }

    return answer;
}

2. 두번째 시도 -> 성공 ⭕ 

function solution(s)
{


	// 문자열의 length가 홀수면 무조건 return 0;
    if(s.length%2){
        return 0;
    }

    var answer = 0;
    let string = [...s]

    let stack=[]

    for(let i=0; i<string.length; i++){
        if(stack[stack.length-1]===string[i]){
           stack.pop()
        }else{
            stack.push(string[i])
        }
    }
    return stack.length?0:1;
}

느낀점🔽

이제 어느정도 로직 작성까지는 만들 수 있는데 그 이후의 시간복잡도를 최적화 하지 못하고 있다. 앞으로 관건은 시간 복잡도를 최적화 하는 것을 목표로 잡고 풀어야 겠다. 그리고 splice에 대한 개념을 다시금 회고하는 시간을 가질 수 있었다.

stack에 대한 기법을 최대한 활용하여 연산속도를 줄이자!!👁‍🗨🕑

 

*Array.splice method ( 참고사항 - splice 는 붙이다 라는 의미로 영어에서 사용 )

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/splice

Array.prototype.splice() - JavaScript | MDN