올바른 괄호
✅ 문제 설명
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
✅ 제한사항
문자열 s의 길이 : 100,000 이하의 자연수
문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
📌 풀이 핵심 (Stack을 사용하게 된 생각의 흐름)
⏰ 풀이 초반
처음 문제를 접했을 때는 단수히 여는 괄호는 +1 닫는 괄호는 -1로 바꿔서 문자열을 순회하며 누적합을 계산해 짝이 맞는지 확인하는 방식으로 진행을 했었다.
이 방식은 간단하고, 빠르게 구현은 가능했지만 2중 For문을 사용하다 보니 테스트 케이스에서 시간 효율성 테스트를 넘지 못했다 😥
⚡ 생각의 전환
이때 떠올렸던 게 Java의 컬렉션 프레임워크였고, 먼저 처음에는 List나 Map 같은 일반적인 자료구조를 생각해봤다.
List는 인덱스 기반으로 순차 저장하기 때문에 열고, 닫는 괄호가 반복적으로 나오는 구조가 아닌 (())() 처럼 중첩되거나 순서에 따라 달라지는 경우 처리가 어렵다고 판단했다.
이후 Map은 키,값 쌍으로 처리되는데 key는 중복이 되지 않고, 하나의 value만 저장 가능 및 순서 보장이 되지 않는다 라는 점으로 처리가 어렵다고 판단했다.
이런 고민들을 통해서 괄호를 체크하기 위한 최적의 방법은 짝을 맞춰서 넣고, 꺼내고가 가능해야 하고 열리면 닫히는 구조를 가지고 있기 때문에 뒤에서 부터 값을 꺼내느 LIFO구조의 Stack 을 떠올리게 되었다.
스택을 사용해 여는 괄호를 쌓아두다가 닫는 괄호가 나왔을 때 가장 마지막 괄호를 꺼내면서 짝을 맞추는 방식으로 코드를 구성했다.
💡 스택으로 구현했을 때의 장점
- 여는 괄호 '('를 만나면 스택에 push하고,
- 닫는 괄호 ')'를 만나면 스택에서 pop을 해서 짝을 맞추는 방식
- 만양 닫는 괄호가 먼저 나왔는데 스택이 비어 있다면,
- 짝이 없는 괄호이기 때문에 즉시 false를 반활할 수 있어 효율적인 예외처리가 가능하다.
🔽 소스코드 1 (stack 사용)
💻 풀이
Stack은 LIFO(Last-In First-Out) 구조이기 때문에 괄호 문제에 아주 적합하다.- 먼저
Stack을 선언해주고 이후 반복문을 사용해 - 여는 괄호 '('를 만나면 스택에 push
- 닫는 괄호 ')'를 만나면 스택이 비어있으면
false그렇지 않으면 pop로 짝을 맞춰준다. - 최종적으로 스택이 비어있는지를 체크해준다.
⌛ 시간 0.12ms ~ 0.24ms
public boolean solution1(String s) {
Stack<Character> st = new Stack<>();
for(char c : s.toCharArray()) {
if(c == '(') {
st.push(c);
}else if(c == ')') {
if(st.isEmpty()) {
return false;
}
st.pop();
}
}
return st.isEmpty();
}🔽 소스코드 2 (반복문 사용 ❌효율성 탈락)
💻 풀이
-
replaceAll을 사용해 열리는 괄호에는 1을 닫히는 괄호에는 -1로 바꿔준다. -
이때
\\를 사용하지 않으면java.util.regex.PatternSyntaxException: Illegal repetition에러를 만나니 주의하자 (관련 포스트 : 에러 해결) -
이후 배열에 하나씩 넣어주는데 이때
trim()으로 공백을 없애고,split("\\s+")로 구분해 넣어준다.
📌 정규식 :\\s: 공백 문자 ,+: 하나 이상 -
만약 시작 괄호가
(이 아니거나 종료 괄호가)이 아닌 경우 반복문을 수행하지 않고 바로false를 return 해준다. -
위 경우가 아닐 경우 반복문을 통해 숫자가 -1 이하가 될 경우
false를 return 하고 -
최종적으로 0이 될 경우에만
true를 return 해준다.
🧡 스택 말고 다른 방법으로 풀어보려고 해봤는데 효율성이 역시나 문제다 ㅠㅠ
⌛ 시간 0.43ms ~ 2.49ms
public boolean solution(String s) {
s = s.replaceAll("\\(", " 1 ");
s = s.replaceAll("\\)", " -1 ");
String[] arr = s.trim().split("\\s+");
if(arr[0].equals(")") || arr[arr.length -1].equals("(")) {
return false;
}
int sum = 0;
for(int i = 0; i < arr.length; i++) {
sum += Integer.parseInt(arr[i]);
if(sum <= -1) {
return false;
}
}
return sum == 0? true : false;
}