성능 요약
-
메모리: 52.8 MB, 시간: 19.78 ms - Answer Code1
-
메모리: 53.1 MB, 시간: 7.90 ms - Answer Code2
구분
코딩테스트 연습 > 스택／큐
Answer Code1(23.02.04)
import java.util.*;
class Solution {
boolean solution(String s) {
// [1] 정답을 저장할 변수로 answer와 stack을 선언
boolean answer = true;
Stack <Character> stack = new Stack<>();
// 반복문을 이용하여 문자열을 앞에서부터 비교
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// [2] 문자를 비교할 때 `(` 일 경우 스택에 push
if(c == '(') {
stack.push(c);
}
// [3] `)`일 경우
if( c == ')') {
// stack의 크기가 0이면 false 반환
if(stack.size() == 0) {
answer = false;
}
// stack의 크기가 0이 아니라면 `(`가 있다는 의미이므로 스택에 pop
else {
stack.pop();
}
}
}
// [4] 문자열을 끝까지 확인한 이후에 스택의 크기가 0이면 true 반환
if(stack.size() != 0) {
answer = false;
}
return answer;
}
}
Answer Code1 - 문제 풀이
-
스택을 이용하여 괄호가 짝을 이룬다면 스택을 제거한다.
-
문자열을 끝까지 검사했을 때 스택의 크기가 0이면 올바른 괄호이므로 true를 반환하고, 그렇지 않으면 false를 반환한다.
-
[1] 정답을 저장할 변수로 answer와 stack을 선언하고, 반복문을 이용하여 문자열을 앞에서부터 비교한다.
-
[2] 문자를 비교할 때
(일 경우 스택에 push 한다. -
[3]
)일 경우 이때, stack의 크기가 0이 아니라면 스택에 pop 한다.- stack의 크기가 0이 아니라면
(가 있다는 의미이고, 스택의 크기가 0이라면(가 없으므로 짝을 이룰 수 없다.
- stack의 크기가 0이 아니라면
-
[4] 문자열을 끝까지 확인한 이후에 스택의 크기가 0이면 true, 아니면 false를 return 한다.
Answer Code2(23.02.04)
class Solution {
boolean solution(String s) {
boolean answer = false;
int count = 0;
for(int i = 0; i<s.length();i++){
if(s.charAt(i) == '('){
count++;
}
if(s.charAt(i) == ')'){
count--;
}
if(count < 0){
break;
}
}
if(count == 0){
answer = true;
}
return answer;
}
}
Review
-
(2번째 풀이) 다른 사람의 풀이를 가져와봤는데, 스택을 사용안하면서 count 변수를 사용하여 깔끔하게 풀이했다.
-
그 결과 1번째 풀이보다 시간적인 측면에서 3배 가까이 시간을 절약하는 것을 볼 수 있었다.
-
스택을 사용한다고 해서 좋은 정답은 아니라는 것을 알 수 있었다.