[JS] 2017 팁스타운 > 짝지어 제거하기

function solution(s){

    var arr = [];
    s = s.split("");
    
    for(var i = 0; i < s.length; i++){
        
        var char = s[i];
        
        if(arr[arr.length-1] == char){
            arr.pop();
        }else{ 
            arr.push(char);
        }      
    }
    return arr.length > 0 ? 0 : 1;
}

이번 문제도 효율성에서 어려움을 겪었다.

입력이 100만인 경우에는 n이나 nLogn 알고리즘을 사용해야 효율성 테스트에서 통과를 할 수 있다고 한다.

시간 알고리즘에 대해서 공부를 해봐야겠다..

 

배열 하나를 선언하고, 문자열 s를 split을 이용해 배열로 만들어준다.

s의 길이만큼 반복을 하고 char 변수에 s배열의 i값을 저장해준다.

그리고 arr배열의 마지막 값과 char의 값이 같다면 arr에 있는 값을 삭제하고, 값이 다르다면 char를 arr 배열에 넣어준다.

 

입력값이 "baabaa"일 때 

맨 처음 char 변수에는 b가 담기게 된다.

arr에는 지금 아무 값이 없으니 push가 되어 arr에 b가 저장된다.

다음 char에는 두 번째 값인 a가 담기게 되고 arr의 마지막 값인 b와 값이 다르기 때문에 다시 push가 된다.

세 번째로 char에 a가 담기게 되고 arr의 마지막 값도 a이기 때문에 pop이 되어 arr 배열에는 b만 남게 된다.

네 번째로 char에 b가 담기고 arr의 마지막 값과 같아서 다시 pop이 되어 arr은 빈 상태가 된다.

남은 aa도 마찬가지로 push가 됐다가 pop이 되어 결국 arr은 빈 상태가 된다.

 

만약에 문자를 모두 지우지 못 한다면 arr의 길이가 0보다 클테니, 이 경우는 0을 반환하고 모든 문자를 지울 수 있다면 길이가 0일테니 1을 반환해주면 된다.

 

function solution(s){

    var len = s.length;

    while(true){
        
        for(var i = 0; i < s.length; i++){

            if(s[i] == s[i+1]){
                s = s.replace(s[i+1], "").replace(s[i], "");
            }
        }
        if(s.length == 0){
            return 1;
        }else if(s.length == len){
            return 0;
        }   
    }    
}

위의 코드는 답은 맞지만 효율성에서 시간초과로 틀린 코드다.

while을 돌려 무한반복을 시키면서 s의 i와 i+1이 같으면 replace를 시켜주는 식으로 코드를 짰다.

replace를 계속 하면서 s의 길이가 0이 되면 1을 리턴하고, 만약에 replace를 계속 해도 s의 길이가 처음의 길이(len)와 같다면 변환이 되지 않으니 0을 반환해준다.