문제
https://school.programmers.co.kr/learn/courses/30/lessons/12909
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
접근 방법 및 풀이
전형적인 Stack 구조를 활용한 문제
Stack을 사용
import java.util.Stack;
public class Q30_12909 {
boolean solution(String s) {
Stack<Character> stack = new Stack<>();
int length = s.length();
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (stack.isEmpty()) {
stack.push(c);
} else if (c == ')' && stack.peek().equals('(')) {
stack.pop();
} else {
stack.push(c);
}
}
return stack.isEmpty();
}
}
정확성 테스트와 효율성 테스트를 모두 통과
효율성 테스트는 평균 약 20ms 소요
Stack을 사용하지 않고 배열을 사용하여 성능 개선
public class Q30_12909 {
boolean solution(String s) {
char[] stack = new char[100000];
int index = 0;
int length = s.length();
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (index == 0) {
stack[index] = c;
index++;
} else if (c == ')' && stack[index - 1] == '(') {
index--;
} else {
stack[index] = c;
index++;
}
}
return index == 0;
}
}
정확성 테스트와 효율성 테스트를 모두 통과 하며 효율성 테스트의 평균 소요 시간은 약 6ms으로 성능 향상