[Codility] Lesson 7: Stacks and Queues - Nesting (javascript) 문제 풀이

깃허브 : https://github.com/miiingo/codility

Task description

원본 사이트 : app.codility.com/programmers/lessons/7-stacks_and_queues/nesting/

Nesting coding task - Learn to Code - Codility

- N 개의 문자로 구성된 문자열 S가 주어짐
- S가 올바르게 중첩되면 1을, 그렇지 않으면 0을 return
- 괄호가 올바르게 닫혀야함
- 가장 효율적인 알고리즘 작성
- N은 [0..1,000,000] 범위 내의 정수
- 문자열 S는 "(" 또는 ")" 문자로만 구성

 

Solution

CASE 1: 왼쪽 괄호를 스택에 저장해 해결 - 100%

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(S) {
    // write your code in JavaScript (Node.js 8.9.4)
    const N = S.length;
    const charOpen = '(';
    const charClose = ')';
    let stack = [];
    
    for(let i=0; i<N; i++){
        if(S.charAt(i) == charOpen){
            stack.push(i);
        }
        if(S.charAt(i) == charClose){
            if(stack.length > 0){
                stack.pop();
            }
            else{
                return 0;
            }
        }
    }
    
    if(stack.length > 0){
        return 0;
    }
    else{
        return 1;
    }
}

- N : 문자열 S의 길이
- charOpen : 왼쪽 괄호(열리는 괄호) 문자
- charClose : 오른쪽 괄호(닫히는 괄호) 문자
- stack : 왼쪽 괄호를 저장할 스택
- 문자열 S의 길이만큼 for문을 돌며 스택에 push 또는 pop
    왼쪽 괄호가 나오면 해당 인덱스를 stack에 저장 -> stack에 저장되는 문자는 모두 왼쪽 괄호이므로 인덱스 값을 stack에 저장(스택에 추가된다는 것이 중요하지 실제 저장되는 내용은 중요하지 않음)
    오른쪽 괄호가 나오면 왼쪽 괄호와 상쇄되어야하기 때문에 stack의 length가 0보다 크면 stack의 top을 pop
    오른쪽 괄호가 나왔는데 상쇄될 왼쪽 괄호가 없는 경우(stack.length가 0보다 작거나 같은 경우), 0을 return
- for문이 종료되면 stack의 length를 확인해 결과 return
    length > 0 : stack에 짝이 맞지 않는 왼쪽 괄호가 남아있다는 소리이므로 0을 return
    length = 0 : stack이 비어있는, 모든 괄호가 짝이 맞는다는 소리이므로 1을 return

 

CASE 1: Result

app.codility.com/demo/results/trainingKATFHN-J5V/

 

CASE 1: Analysis

The solution obtained perfect score.
이 솔루션은 완벽한 점수를 얻었습니다.

 

결론

이 문제는 이전에 풀었던 Lesson 7: Stacks and Queues - Brackets 문제와 비슷한데 괄호의 종류가 한 가지이기 때문에 비교적 더 쉬웠던 문제다.

stack에는 왼쪽 괄호 '('만 저장되기 때문에 비교할 수 있게끔 문자의 위치를 넣어줬는데 stack의 length가 중요한 것이기 때문에 넣는 데이터는 크게 상관이 없다.
오른쪽 괄호 ')'가 나오면 왼쪽 괄호를 상쇄시키고, 상쇄시킬 왼쪽 괄호가 없으면 0을 return한다.
그리고 for문이 종료되고 나면 stack이 비어있는지 확인해 비어있지 않으면 0을, 비어있으면 1을 return하면 된다.