프로그래머스 - 짝지어 제거하기

 

처음에 생각한 방법은 함수를 따로 빼 중복 확인을 하고, 중복 제거를 위해 splice를 사용하는 방법이었습니다.

그렇게 짠 코드는

function solution(s)
{
    return check(s).length == 0 ? 1 : 0
}

function check(s){
    let str = s.split('')
    for(let i = 0; i<str.length; i++){
        if(str[i] === str[i + 1]) {
            str.splice(i, 2)
            i = -1
        }
    }
    return str
}

 

i를 -1로 준 이유는 1로 주면 i++ 때문에 0부터가 아닌 1부터 배열이 돌기 때문이었습니다.

이 코드의 문제는 -1로 돌아감으로써 불필요한 반복이 늘어났습니다. 따라서 효율성 테스트를 통과하지 못 했습니다. 그래서 생각한 방법은 

 

stack을 사용하는 방법입니다.

 

stack은 LIFO (Last In First Out)의 형태입니다. 따라서 나중에 넣은 데이터가 먼저 나오게 됩니다.

 

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

 

stack이 비어있거나 stack 안의 마지막 값이 s[i]과 다르면 stack에 s[i] 값을 넣어줍니다. 만약 stack에 값이 들어있고, stack 안의 마지막 값과 s[i]이 같다면 stack의 마지막 값을 제거해줍니다. (중복 제거)

 

이 과정을 통해 마지막 stack의 길이를 확인해 만약 stack에 값이 들어있다면 짝지어 제거하기가 실패했기 때문에 0을, 값이 들어있지 않다면 성공했기 때문에 1을 리턴해줍니다.

 

오늘의 코테는 여기서 마무리~ 

그럼 20000~