[Codility 문풀] Nesting

Codility 문제 - Nesting

문자열 S를 구성하는 각각의 문자들이 서로 중첩되어 있을 경우 1을, 서로 중첩되어 있지 않을 경우 0을 반환

 

■ 문제 풀이

1) 문풀 설명
- "(", ")"로만 구성된 문자열이 있음
- 문자열의 길이(N)의 범위는 [0...1,000,000]
- 주어진 문자열의 각 문자가 서로 중첩이 될 경우 1을, 중첩되지 않는 경우가 있을 경우 0을 반환

2) 예제
String S = "(()(()())" 이 주어진 경우, 1을 반환
String S = "())" 이 주어진 경우, 0을 반환

3) 힌트
Stack을 사용
앞선 Brackets 문제와 같은 유형임

 

import java.util.Stack;

public class Nesting {
    static int solution(String S){
        Stack st = new Stack();
        char[] ch = S.toCharArray();

        for(int i=0; i<ch.length; i++){
            if(ch[i] == '(' || st.isEmpty()){
                st.push(ch[i]);
            }else{
                String chek = st.peek().toString();
                if(!(chek.equals("(") && ch[i]==')')){
                    return 0;
                }
                st.pop();
            }
        }

        return st.isEmpty() ? 1:0;
    }

    public static void main(String[] args) {
        String S = "())";
        System.out.println("Nesting result : " + solution(S));
    }
}