Codility Lesson 07 - Nesting( JAVA )

https://app.codility.com/programmers/lessons/7-stacks_and_queues/nesting/

Nesting coding task - Learn to Code - Codility

 

문제

- 하위의 조건에 부합하면 N개의 문자들로 이루어진 S문자열은 적절하게 중첩되었다고 한다.

• 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.

S가 비어있거나, (U)에 둘러쌓여 있거나, VW형태 일 경우( U, V, W는 모두 적절히 중첩된 문자열들을 의미 )

- 예시 : "(()(())())" : properly nested /  "())" : not properly nested

- 적절히 중첩된 경우 return 1, 그렇지 않은 경우 return 0

 

제한조건

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

N은 0 ~ 1,000,000 사이의 정수이다.

S는 '(', ')'로 이루어져 있다.

 

풀이

- S가 홀수 일경우와 0일 경우는 예외처리 해준다( 0일 경우 return 1, 홀수 일 경우 return 0 )

- int answer = 1로 초기화( 후에 for문을 순회하면서 적절한 중첩이 아닌 경우 0으로 바꿈 )

- stack 자료구조를 활용하여 풀이한다.

- '(' 일때는 stack에 push / ')'일 때는 stack.size()를 확인하여 있으면 pop, 없으면 answer = 0 후 break

- for문을 전부 순회 후 stack.size()가 0일 경우 answer = 1, 그렇지 않으면 answer = 0

 

예상 시간복잡도 : O(N) - for문 모두 순회

 

소스코드

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(String S) {
        // write your code in Java SE 8
        if( S.length() == 0 ) return 1;
        else if( S.length() % 2 == 1) return 0;

        Stack<Character> stack = new Stack<>();
        char[] sArr = S.toCharArray();
        int answer = 1;

        for( char c:sArr ){
            if( '(' == c ) stack.push(c);
            else{
                // ')'일 경우
                if( stack.size() == 0 ){
                    answer = 0;
                    break;
                }else{
                    stack.pop();
                }
            }
        }

        if( stack.size() != 0 ) answer = 0;
        return answer;
    }
}

 

번외

- '(', ')'의 개수만 맞으면 되지 않나..?

- S.length가 0일 때와 홀 수일 때 예외처리 동일

- for문을 순회하며 '('와 ')' 개수를 확인 -> 둘의 개수가 맞으면 return 1, 맞지 않으면 return 0

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(String S) {
        // write your code in Java SE 8

        if( S.length() == 0 ) return 1;
        else if( S.length() % 2 == 1) return 0;

        char[] sArr = S.toCharArray();
        int count = 0;
        for( char c : sArr ){
            if( c == '(' ) count++;
            else count--;
        }

        if( count == 0 ) return 1;
        else return 0;

    }
}

방향성이 관계가 없어짐으로 코너케이스가 생김

 

번외 - 보완

- char c == ')'일 경우 count가 0 이하일 때를 분기해줌( 결국은 stack으로 풀이했을 때와 같은 수순 )

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(String S) {
        // write your code in Java SE 8

        if( S.length() == 0 ) return 1;
        else if( S.length() % 2 == 1) return 0;

        char[] sArr = S.toCharArray();
        int count = 0;
        for( char c : sArr ){
            if( c == '(' ) count++;
            else{
                if( count <= 0 ){
                    count = -1;
                    break;
                }else{
                    count--;
                }
            }
        }

        if( count == 0 ) return 1;
        else return 0;

    }
}