올바른 괄호

문제

문제 설명

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

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

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

제한사항

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

입출력 예

s	answer
"()()"	true
"(())()"	true
")()("	false
"(()("	false

입출력 예 설명

입출력 예 #1,2,3,4
문제의 예시와 같습니다.

---

나의 풀이

시도한 방법

1. 스택을 사용 -> 효율성 테스트 실패
2. int 사용

풀이법
실패하는 경우를 먼저 생각하고 이외의 경우 성공으로 취급했다.
실패하는 경우
1. ( 개수가 많다.
2. ) 개수가 많다.
3. (, ) 개수는 맞지만 순서가 맞지 않는다.

풀이 내용
1. ( -> stack/int에 값을 넣는다.
2. ) -> stack/int에서 값을 뺀다.
2.1. stack이 비었거나 int가 0인 경우: 앞서 연달아 들어왔던 ( 개수보다 ) 개수가 많다. -> 실패하는 경우 2., 3. 해결
2.2. String 끝까지 검증한 후 stack/int를 확인한다 -> ( 개수가 많은 경우 stack이 비어있지 않음/ int > 0

구현
1. Stack

class Solution {
	public boolean solution(String s) {
		 Stack<String> stack = new Stack<>();

		for (int i = 0; i < s.length(); i++) {
			String input = Character.toString(s.charAt(i));
			if (input.equals("(")) {
				stack.push(")");
			} else if (input.equals(")")) {
				if (stack.empty()) {
					return false;
				}
				stack.pop();
			}
		}
		return stack.empty();
	}
}

정확성 테스트는 성공. 효율성 테스트에서 실패.
클래스 -> primitive type 사용으로 시간 단축.

2. int

class Solution {
    public boolean solution(String s) {
		int count = 0;

		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '(') {
				count++;
			} else {
				if (count == 0) {
					return false;
				}
				count--;
			}
		}

		return count == 0;
	}
}