인프런 커뮤니티 질문&답변
작성한 질문수
스택을 사용하기 했는데 효율성이 떨어지는 거 같아 리뷰 요청드립니다~
작성
·
341
·
수정됨
0
function solution(a){
let answer=0
let stack = []
let stick = []
let laser = []
// 막대 내 속한 레이저의 갯수 + 1이 최종 막대 갯수
// 막대 한 개 안에 속한 레이저가 총 몇개인지 구해서 카운트 더하기
for(let x=0; x<a.length; x++){
//막대 시작
if(a[x]==="(" && a[x+1] !==")"){
stack.push(x)
}
// 막대 끝
if(a[x]===")" && a[x-1] !=="("){
const pair = stack.pop()
stick.push([pair,x])
}
//레이저인데 막대 내부에 있는 레이저인 경우
if(a[x]=="(" && a[x+1]==")" && (a[x-1]=="(" || a[x+2]==")")){
laser.push(x)
}
}
for (let i = 0; i < stick.length; i++) {
const start = stick[i][0];
const end = stick[i][1];
let cnt = 0
for (let j = 0; j < laser.length; j++) {
if (laser[j] > start && laser[j] < end) {
cnt++
}
}
answer += cnt+1
}
console.log(stick,laser)
return answer
}
let a="()(((()())(())()))(())";
console.log(solution(a)); 이렇게 하다 보니 이중 for문을 사용해 복잡도가 n2이 되버려서 효과적이지 못한거같습니다.. 이런 접근 법은 별로일까요
답변 1
0
김태원
지식공유자
안녕하세요^^
접근법의 아이디어는 스택이 아니어도 되는 방법이라 참신하고 좋습니다. 다만 스택을 쓰는 것보다 약간 효율성이 떨어지는게 좀 그렇지만 괄호문자열의 길이가 10,000정도라면 이 방법도 좋은 방법으로 보입니다.
이런 아이디어를 생각해내는 것만으로도 나중에 굉장한 실력자가 될 것 같습니다. ㅎㅎ
아래는 반례입니다. 다 좋은데 레이저를 찾는데서 약간 실수가 있어 보입니다. 레이저를 막대기 내부 외부 구분하지 말고 그냥 다 찾아버리는 게 좋을 것 같습니다. 어자피 막대기 외부에 있는 레이저는 카운팅하지 않게 2중for에서 한 것 같은데요.
아래 입력의 정답은 21입니다.
let a="(((()()((()())))))";
console.log(solution(a));