Codility Lesson7 - Nesting

🔍 문제

---

이전에 풀었던 Lesson7의 Brackets와 매우 비슷한 문제인데 더 쉬운 문제이다. (, ) 로 이루어진 문자열 S의 괄호 짝이 맞는지 확인해서 맞으면 return 1 틀리면 return 0을 하면 된다.

 

Nesting coding task - Learn to Code - Codility

 

✏️ 풀이 - JS

---

이 문제도 역시 stack을 이용해서 풀었다. 여는 괄호가 나오면 open이라는 배열에 넣어주고, 닫는 괄호가 나오면 open.pop()을 해서 여는 괄호가 있는지 확인해주면 된다. 처음에는 주어진 문자열 S를 배열로 변환해주지 않고 문자열에서 for문을 돌려 아래와 같이 풀었다.

function solution(S) {
    let open = [];

    if(S === '') return 1;

    for(let i in S) {
        if(S[i] === '(') {
            open.push('(');    
        } else if (S[i] === ')'){
            if(open.pop() !== '(') return 0;
        }
    }

    if(open.length === 0) {
        return 1;
    } else {
        return 0;
    }
}

하지만 아래와 같이 performance 부분에서 타임아웃 에러가 떴다.

 

 

아주 미세한 차이로 타임아웃 에러가 나서 어떻게 줄여볼까하다가 문자열 S를 아예 배열로 바꿔준뒤에 for문을 돌렸더니 통과할 수 있었다. 문자열 S를 배열처럼 쓰려고 하다보니 그 과정에서 어떤 추가적인 동작이 실행되면서 시간이 늘어나는 것 같다. 시간복잡도는 둘다 O(N)이 나왔다.

function solution(S) {
    let open = [];
    const arr = S.split('');

    if(S === '') return 1;

    for(let i in arr) {
        let c = arr[i];
        if(c === '(') {
            open.push('(');
        } else if (c === ')'){
            if(open.pop() !== '(') return 0;
        }
    }

    if(open.length === 0) {
        return 1;
    } else {
        return 0;
    }
}

0.384s 에서 0.228s로 줄어든 모습을 볼 수 있다.