풀이
김영준
function solution(s){ let open = 0; for(const value of s){ if (value === "("){ open++; } else { if (open === 0) return false; open--; } } return open ? false : true } // open 변수를 열린 괄호면 +1 닫힌 괄호면 -1 하는 로직으로 구현했고, // 만약 처음부터 닫힌 괄호가 나오면 바로 false를 리턴하게 했습니다. // open === 0 이면 모든 괄호가 닫혔기 때문에 true를 리턴하고 아니면 false를 리턴했습니다. function solution(s){ const stack = []; for(let v of s){ if (v === "("){ stack.push(v); } else { if(stack.length === 0) return false; stack.pop(); } } return stack.length === 0; } // 다음 강의에서 강사님이 스택으로 푸시길래 스택으로 푼 것도 올립니다. // 로직은 변수를 증감 시키는 것 대신 stack을 push, pop 하는 형식으로 변경했고 // 예외 처리는 똑같이 첫 번째 원소가 닫힌 괄호면 바로 false를 리턴하게 했습니다.
이종현
function solution(s){ // stack에 사용될 빈 배열 선언 const arr = []; // 문자열s의 길이만큼 반복문을 돌면서 stack의 마지막 원소가 '('이고 // 문자열s의 현재 index가 ')'라면 stack의 마지막 원소를 pop해주고 // 아니라면 stack에 push해준다. for (let i = 0; i < s.length; i++) { if (arr[arr.length - 1] === '(' && s[i] === ')') { arr.pop(); } else { arr.push(s[i]); } } // 반복문을 완료하고 stack의 길이를 확인한다. // 길이가 0이라면 ture를 반환 아니라면 false를 반환한다. if (!arr.length) return true; else return false; }
박노철
function solution(s){ const ar=[]; //배열이 비어있는데 ')' 는 올 수 없다. if(s.length%2===1)return false //전체 길이가 짝수가 아니라면 false; let flag = true; for(let i of s ){ if(i==="("){ ar.push(i); }else{ if( ar.length===0 )flag=false; else ar.pop(); } if(!flag)break; } //모두 검사했는데 열린괄호가 남아있다면 false return (ar.length===0 && flag)? true: false; }
이민희
function solution(s){ var answer = true; // 괄호를 순차적으로 스택에 쌓아놓고, 위에서부터 (기존 문자열의 뒤쪽) 하나씩 꺼냅니다. const stack = Array.from(s); let cnt_close = 0; // 꺼낸 괄호가 닫는 괄호일 경우 개수를 1 증가시킵니다. while (stack.length !== 0) { let top = stack.pop(); // 1. 꺼낸 괄호가 닫는 괄호일 경우 cnt_close에 개수를 1 증가시킵니다. if (top === ")") { cnt_close += 1; } /* 2. 꺼낸 괄호가 여는 괄호일 경우, cnt_close가 0이 아니라면 (꺼내놓은 닫는 괄호가 있다면) 짝을 이룰 수 있는 것이므로 cnt_close를 1 차감시킵니다. */ else if (top === "(" && cnt_close !== 0) { cnt_close -= 1 // 짝을 이루었으므로 개수 1 차감 } /* 3. 꺼낸 괄호가 여는 괄호일 경우, cnt_close가 0이라면 (꺼내놓은 닫는 괄호가 없다면) 짝을 이룰 수 없으므로 false를 반환합니다. */ else { answer = false; break; } } if (cnt_close != 0) answer = false; return answer; }
박건우
function solution(s){ let cnt = 0; for(let x of s){ if(x === "("){ cnt += 1; }else{ if(cnt === 0) return false; else cnt -= 1; } } return (cnt === 0); } // 스택 안쓰고도 풀 순 있습니다. 마지막 괄호가 무엇이었는지 기억을 안해도 되기 때문이에용. // 단순히 열린 괄호의 개수만 기억하면 됩니다. // 닫힌 괄호가 나오면 카운트를 1 감소합니다. // 이 풀이가 제일 빠르고 항상 통과합니다. function solution(s){ let stack = []; let cnt = 0; for(let x of s){ if(x === "(") { if(stack.length > s.length - cnt) return false; stack[stack.length] = x; } else{ if(!stack.length) return false; else stack.pop(); } cnt+=1 } return (stack.length === 0); } // 이 코드는 스택을 써서 푼 것이긴 한데 // 효율성 검사에서 어떨때는 통과하기도 어떨때는 틀리기도 합니다. // 그래서 연결리스트가 더 빠른가? 해서 연결리스트로도 해봤는데 더 느리더라구요 // 2가지 예외를 생각해야 되는것 같아요 // 스택에 쌓인 "(" 개수가 남은 괄호 개수보다 더 많으면 바로 false 리턴 // ")" 가 나왔는데 스택이 비어있다면 바로 false 리턴 // 강사님이랑 똑같이 작성했는데도 혹시 저만 효율성에서 탈락하나요..?
박주연
function solution(s){ let stack = []; for (const i of s){ if(i === "("){ stack.push("("); } else if(i === ")") { if(stack.length != 0 && stack[stack.length-1] ==="("){ stack.pop(); }else{ //stack이 비어있거나 stack의 마지막 요소가 (가 아닌경우 stack.push(")"); // 이코드를 return false;로 바꿔주니 효율성 문제 해결 } } } return stack.length === 0 ? true: false ; }
이렇게 풀었는데 테스트케이스는 다 맞아도 효율성에서 탈락했어요. 그래서
stack.push(")");이 부분을 굳이 스택에 넣지 않고 바로 false 리턴되게 바꿨더니 효율성과 테스트케이스 모두 성공으로 뜨네요. 아마 제가 처음에 짠 코드처럼 스택에 또 ‘)’를 넣어주면 메모리 저장이 많아져서 효율성이 실패로 떴던 것 같아요 🙂