[프로그래머스 Java] 올바른 괄호

1. 문제

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 

예를 들어

"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항
문자열 s의 길이 : 100,000 이하의 자연수
문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다

 

2. 풀이

1) 효율성 테스트 통과 x

class Solution {
    // ( 로 열렸으면 반드시 짝지어서 ) 로 닫혀야 한다.

    boolean solution(String s) {
        
        int start = 1;
        int end = 0;  
        
        String [] tmp = s.split("");
                
        // 1. ( 로 시작해야함
        if(tmp[0].equals(")")){
            return false;
        }

        for(int i=1; i< tmp.length; i++){
            if(tmp[i].equals("(")){
                start += 1;
            }else{
                end += 1;
            }
            
            // 2. ) 숫자는 항상 ( 보다 작거나 작아야 함 (매번 검사)
            if (end>start) {                                
                return false;   
            }
        }
        
        // 3. 끝나는 숫자는 항상 (,) 가 같아야 함
        if (end==start) {
            return true;
        }else{
            return false;
        }
    }
}

 

2) 효율성 테스트 통과

class Solution {
    boolean solution(String s) {
        int start = 1;
        int end = 0;
        
        for(int i = 1; i<s.length(); i++){
            if(s.charAt(i) == '('){
                start++;
            }
            
            if(s.charAt(i) == ')'){
                end++;
            }
            
            if(start < end){
                return false;
            }
        }
        
        if(start-end == 0)return true;        
        else return false;
    }
}

 

3) Stack 활용

import java.util.*;

class Solution {
    boolean solution(String s) {
        
        Stack<Integer> stk = new Stack<>();
        
        for(int i=0; i < s.length(); i++){
            if(s.charAt(i)=='('){
            stk.push(1);
            } else if (s.charAt(i)==')'){
                if(stk.isEmpty()) return false;
                else stk.pop();
                
                }
            }
            
        if(stk.isEmpty()) return true;
        else return false;
        
        }            
}

3. 배운 내용

1) "" 와 '' 차이: "" 는 String 클래스 자료형, '' 는 char 원시 자료형. char 는 한글자만 담을 수 있다.

2) 향상된 for문: String 배열의 경우 다음과 같이 향상된 for문 사용할 수 있다

public class Split {
 
	public static void main(String[] args) {
		String str1 = "너에게 난 뭐냐";
		String[] words = str1.split("\\s");
		
		for (String wo : words ){
			System.out.println(wo);
		}
	}
}

// 출력 결과
너에게
난
뭐냐

3) equals: Strnig 타입의 경우 참조 객체기 때문이므로 문자열 비교시 str1.equals(str2)를 사용

4) String.charAt(i): String 에서 인덱스 i에 있는 문자 반환

5) Stack 은 후입 선출로 요소를 저장하는 자료구조

6) Stack.push(): 요소를 스택 맨위에 추가, Stack.pop(): 맨 위의 요소 제거 및 반환, Stack.peek(): 맨 위의 요소 반환(제거x)

7) Stack.isEmpty(): Stack 이 비어있는지 확인 메서드