문제

문제 설명
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

제한사항
문자열의 길이 : 1,000,000이하의 자연수
문자열은 모두 소문자로 이루어져 있습니다.

입출력 예
s result
baabaa 1
cdcd 0

처음 시도, 시간 초과

function solution(s){
    let i=0
    while(i<s.length){
        if(s[i] === s[i+1]){
            i === 0 ? s=s.slice(i+2) : s=s[i-1]+s.slice(i+2)
            i = 0
        }else{
            i++
        }
    }
    return s === "" ? 1 : 0
}

주어진 문장 s를 직접 순회하여 인접한 인덱스값을 순서대로 비교하여
잘라내고 붙이는 방식으로 구현해보았으나 문자열 최대 길이가 100만인 것을 감안하면 당연하게도 시간초과가 발생한다.
더 나은 방법을 찾기 위해 다른 사람의 풀이를 참조했다.

solution

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

1. 문자열의 길이가 홀수라면 항상 짝이 안 맞으므로 0을 반환한다.
2. t는 선입후출(=후입선출)의 구조를 가지는 스택(Stack)이다.
3. s를 순회하여 s[i]와 t의 마지막 값(Last In)을 서로 비교한다.

• 다르면 짝이 맞지 않으므로 s[i]를 t에 추가한다
• 같으면 짝이 맞으므로 t에서 마지막 값(Last In)을 제거한다

for...in, for...of 보다 for문이 효율에 좋다