처음에는 주어진 문자열을 조작하면서 while문을 순회하기 시작했는데테스트 코드는 모두 통과가 되었지만 효율성 검사에서 시간초과라는 에러를 발생시켰다.
function solution(s){
let check_index = 0 ;
while(check_index < s.length-1){
// s 자체를 조작하면서 반복문 순회
if(s[check_index] === s[check_index+1] ){
s = s.slice(0, check_index) + s.slice(check_index+2, s.length);
check_index = 0 ;
} else{
check_index += 1;
}
}
// 남아있는 s가 있으면 0 없으면 1로 반환
if(s.length === 0)
return 1
else
return 0
}
이를 해결하기 위해 스택 2개 구현을 통해 반복문 조건을 바꿔보았지만 여전히 작동되지 않았다
function solution(s){
let check_index = 0 ;
// 비교 스택, 문자열 스택을 생성 한뒤
let stack = [], s_stack = s.split('');
while(s_stack.length != 0){
// 비교 스택의 마지막 값과 문자열 스택의 처음 값을 비교하면서 스택 조작
if(stack[stack.length-1] === s_stack[0]){
stack.pop();
} else {
stack.push(s_stack[0]);
}
s_stack.shift();
}
// 비교스택에 원소가 아무것도 없으면 모두 제거된것
if(stack.length ===0){
return 1;
}else {
return 0;
}
}
배열 2개를 반복해서 돌리는 것 자체가 크기에 의한 시간초과를 가져온다고 생각하여
스택 1개만을 사용하여 코드를 구현하였더니 해결이 되었다!!
따라서 최종 답안은 다음과 같다👇
function solution(s){
// 답안 스택
let stack = [];
// s의 길이 만큼 반복
for(let i = 0 ; i < s.length ; i++){
// 답안 스택의 마지막 원소가 비교할 문자열의 문자와 같으면
// 답안 스택의 마지막 원소를 제거
if(stack[stack.length-1] === s.charAt(i)){
stack.pop();
} else {
// 그게 아니라면 원소를 넣어줌
stack.push(s.charAt(i));
}
}
// 모든 반복문이 끝난후 스택에 아무런 원소가 존재하지 않으면
// 모두 제거된 것이므로 1을 반환
if(stack.length ===0)
return 1;
else
return 0;
}
처음에 시도했을 때, 배열 두개를 여전히 사용하였으며 이는 역시 시간초과를 일으켰다
그래서 첫번째 시도했을때의 실수를 떠올려 배열을 한개만 사용하여 진행하였다
달랐던 부분은 checkStack에 값을 넣을때, charAt을 사용하지 않고 [ ] 값의 참조를 통하여 더 단순한 코드로 로직을 구현하였다
최종 코드는 다음과 같다👇
function solution(s) {
const checkStack = [];
// 주어진 문자열 길이동안 반복하면서
//checkStack의 마지막 원소와 문자열 s[i]가 가리키는 문자가 같으면 스택에서 제거하고
// 다르다면 스택에 넣어주기
for (let i = 0; i < s.length; i++) {
if (checkStack[checkStack.length - 1] === s[i]) {
checkStack.pop();
} else {
checkStack.push(s[i]);
}
}
// 스택의 첫번째, 두번째 원소가 같으면 문자열이 모두 제거 되지만,
// 그게아니라면 짝지어 제거하기 실패
if (checkStack[0] === checkStack[1]) {
return 1;
} else {
return 0;
}
}