짝지어 제거하기(level2)

링크

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

문제

알파벳 소문자로 이루어진 문자열이 주어질 때, 연속하는 2자의 알파벳이 오면 해당 알파벳 두 글자를 삭제한다. 삭제 후에 다시 연속하는 2자의 알파벳이 오면 또 그 두 글자를 삭제한다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성하라. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 반환하라.

예제로 이해

문자열 S가 'abbabb' 일 때 앞에서부터 비교를 한다. 비교를 하며 같은 문자가 연속되면 제거한다. 2, 3번 째에 'b'로 같은 문자가 오기때문에 제거하여 'aabb'를 가져온다. 1, 2번 째에 'a'로 같은 문자가 연속하므로 제거하여 'bb'를 가져온다. 1, 2번 째에 'b'로 같은 문자가 연속하므로 제거하여 빈 문자열을 가져온다.

결과적으로 만들어진 문자열이 빈 문자열이므로 성공적으로 수행하였으므로 1을 반환한다.

코드

function solution(s) {
    let arr = s.split("")
    let stack = []
    stack.push(arr.shift())
    
    for(let i = 0; i < arr.length ; i++) {
        if(stack[stack.length - 1] === arr[i]) {
            stack.pop()
        } else {
            stack.push(arr[i])
        }
    }
    
    if(stack.length === 0) return 1
    else return 0
}

코드 풀이

이 문제는 문제 해결을 위한 효율상의 문제로 스택을 활용하여 가장 위에 있는 문자와 다음에 올 문자를 비교하여 같은 문자가 오면 스택에 쌓여있는 것을 제거하고, 같은 문자가 오지 않는다면 스택에 쌓는 방식으로 문제를 해결한다.

가장 먼저 문자열을 배열로 바꿔주고, 스택처럼 활용하기 위한 배열을 하나 선언해준다.

그 이후 반복문을 돌려 같은 문자가 오는지를 비교한다.

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

반복문의 로직은 스택의 가장 위에 쌓인, 즉 배열의 마지막 값이 문자열에서 뽑아온 값과 같다면 스택에서 제거해주고, 같지 않다면 스택에 값을 넣어준다.

이 과정에서 스택에 계속 쌓이더라도 끝에 가서는 같은 문자가 나와 제거될 수 있으므로 반복문을 중간에 끊지 않도록 한다.

반복문이 모두 종료되면 스택의 길이에 따른 조건문을 작성하여 stack.length가 0이면 1을 반환, 아니면 0을 반환하도록 한다.