'Algorithm'에 해당되는 글 23건

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 consists only of the characters "(" and/or ")".

  이 문제는 보자마자 두 가지 방식으로 구현해보았다.

(1)  '(' 가 들어올때마다 Stack에 Push 하고 ')' 가 들어올 때마다 Pop 해준다. Pop을 해줄 상황에서 Stack의 원소가 비어있지만 않으면 계속해서 진행하고 비어있을 경우엔 0 을 return 한다. 마지막에 Stack 에 원소가 남아있을 경우 또한 0을 return한다. 이 코드의 장점은 직관적이란 점이다.

import java.util.*;

class Solution {
    public int solution(String S) {
        
        Stack<Character> leftB = new Stack<>();
        
        for(int i = 0; i < S.length(); i++ ){
            
            if(S.charAt(i) == '(' ){
                leftB.push('(');
            }
            else{
                if(leftB.empty()){
                    return 0;
                }
                leftB.pop();
            }
        }
        
        if(!leftB.empty() ){
            return 0;
        }
        
        return 1;
    }
}

(2) 문제에서 사용되는 원소가 '(' 와 ')' 로 서로 대응되는 관계이기 때문에 변수 하나로도 충분히 구현이 가능하다고 생각했다. 그렇게 구현할 경우 while 문을 이용하여 더 간단한 코드로 만들수 있을것 같았다. 이 코드의 장점은 간단한 코드 구성이다.

class Solution {
    public int solution(String S) {
        
        int tmp = 0;
        int idx = 0;
        
        while(tmp >= 0 && idx < S.length() ){
            if(S.charAt(idx) == '('){
                tmp++;
            }
            else{
                tmp--;
            }
            idx++;
        }
        
        if(tmp == 0){
            return 1;
        }
        return 0;
    }
}