[Codility] Lesson7 - Stacks and Queues : Nesting

Problem

A string S consisting of N characters is called properly nested if:

• S is empty;
• S has the form "(U)" where U is a properly nested string;
• S has the form "VW" where V and W are properly nested strings.

For example, string "(()(())())" is properly nested but string "())" isn't.

Write a function:

int solution(string &S);

that, given a string S consisting of N characters, returns 1 if string S is properly nested and 0 otherwise.

For example, given S = "(()(())())", the function should return 1 and given S = "())", the function should return 0, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..1,000,000];
• string S consists only of the characters "(" and/or ")".

How to solve

- 정보

'(' or ')'로 이루어진 배열 A

 

- 구해야 하는것?

( )로 이루어진 닫힌 배열 return 1, 아니면 0 

 

- 풀이

(나올 때 stack 에 push,

) 인경우 stack 이 비어있으면 return 0, 비어있지 않으면 stack pop

S 전체에 대해 순회한 후, 

stack이 비어있으면 return 1, 비어있지 않으면 return 0

Solution(c++)

// you can use includes, for example:
#include <bits/stdc++.h>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(string &S) {
    // write your code in C++14 (g++ 6.2.0)
    int len = S.length();
    stack<char> st;

    for(int i=0; i<len; i++){
        if(S[i] == '('){
            st.push(S[i]);
        }else{
            if(!st.empty()){
                st.pop();
            }else{
                return 0;
            }
        }
    }

    if(st.empty()){
        return 1;
    }else{
        return 0;
    }
}

Test Result

app.codility.com/demo/results/trainingW4RC5R-CWV/

Test results - Codility