Codility_Nesting

7-3. Nesting

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:

class Solution { public 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 is made only of the characters '(' and/or ')'.

문자열 S가 N개의 문자로 구성되어 있을 때, 다음 조건을 만족하면 S는 올바르게 중첩된 문자열이라고 합니다:

S가 비어있다.
S가 “(U)” 형태를 가지며, 여기서 U는 올바르게 중첩된 문자열이다.
S가 “VW” 형태를 가지며, 여기서 V와 W는 올바르게 중첩된 문자열이다.
예를 들어, 문자열 "(()(())())"는 올바르게 중첩된 문자열이지만, 문자열 "())"는 그렇지 않습니다.

다음과 같은 함수를 작성하세요:

class Solution { 
    public int solution(String S); 
}

이 함수는 N개의 문자로 구성된 문자열 S가 주어졌을 때, 문자열 S가 올바르게 중첩된 경우 1을 반환하고, 그렇지 않은 경우 0을 반환해야 합니다.

예를 들어, S = "(()(())())"가 주어지면 함수는 1을 반환해야 하고, S = "())"가 주어지면 함수는 0을 반환해야 합니다.

다음 가정을 만족하는 효율적인 알고리즘을 작성하세요:

N은 [0…1,000,000] 범위 내의 정수입니다.
문자열 S는 오직 '('와 ‘)’ 문자로만 구성됩니다.

문제풀이

ort java.util.*;

class Solution {
    public int solution(String S) {
        int length = S.length();
        int setCount = 0;
        String[] array = S.split("");
        Stack<String> stack = new Stack<>();

        if(length == 0){
            return 1;
        }
        for(int i = 0; i < length; i++){
            if(array[i].equals("(")){
                stack.push(array[i]);
                setCount++;
            }else{
                if(setCount != 0){
                    stack.pop();    
                    setCount--;
                }else{
                    return 0;
                }
            }
        }
        if(setCount == 0){
            return 1;
        }
        return 0;
    }
}

arraylist(문자열 잘라서 저장)과 stack을 사용하여
짝이 맞는 경우에는 1을 리턴
짝이 맞지 않는 경우에는 0을 리턴해줌

제출결과

75%의 정답률

타임 아웃에러 발생으로 코드를 수정하였음

수정코드

import java.util.*;

class Solution {
    public int solution(String S) {
        int length = S.length();
        Stack<Character> stack = new Stack<>();

        if (length == 0) {
            return 1;
        }
        for (int i = 0; i < length; i++) {
            char currentChar = S.charAt(i);
            if (currentChar == '(') {
                stack.push(currentChar);
            } else {
                if (!stack.isEmpty()) {
                    stack.pop();
                } else {
                    return 0;
                }
            }
        }
        return stack.isEmpty() ? 1 : 0;
    }
}

배열에 String을 분리하여 저장하지 않고
char currentChar = S.charAt(i);를 사용,
Stack은 String타입이 아닌 Character 타입으로 변경
setCount변수를 사용하지 않고 stack의 크기만 확인하였습니다.

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/7-stacks_and_queues/nesting/