문제 설명
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 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만인 것을 감안하면 당연하게도 시간초과가 발생한다.
더 나은 방법을 찾기 위해 다른 사람의 풀이를 참조했다.
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 ;
}
t
는 선입후출(=후입선출)의 구조를 가지는 스택(Stack)이다.s
를 순회하여 s[i]
와 t
의 마지막 값(Last In)을 서로 비교한다.s[i]
를 t
에 추가한다t
에서 마지막 값(Last In)을 제거한다 for...in, for...of 보다 for문이 효율에 좋다