스택 알고리즘에서 자주 다루는 () 괄호 문제.
전공 책만 봐도 기본으로 나오는 예제인 것 같다.
그래서 막힘없이 술술 풀릴정도라, 왜 LV2인지는 모르겠으나.. 안 접해본 사람이라면 고민은 해볼 수 있을정도!
본론으로 들어가자면..
스택 (Stack)
- 후입선출(LIFO) 방식의 자료구조.
- 즉, 나중에 들어간 것이 가장 먼저 나오는 구조이다.
이 스택을 어떻게 괄호 문제에 활용할 수 있을까?
괄호가 열리면, 반드시 짝이되는 닫는 괄호가 있어야 한다.
괄호가 열릴 때마다 저장해 두었다가 닫는 괄호를 만나면 하나씩 삭제해 나가면 된다.
만약 열린 괄호의 내역이 없는데, 닫힌 괄호를 만난다면 ? 열린괄호가 없었으므로 닫힌 괄호는 올수없고 이는 규칙을 위반한 사례이므로 false를 반환한다.
그럼 열린 괄호를 어떻게 저장할 수 있을까?
바로 스택을 활용한다.
문자열 타입의 빈 스택을 생성해두고, 인자로 받은 (,)로만 이루어진 문자열 s의 첫번째 문자부터 순회한다.
문자가 열린괄호 ( 이면 스택에 넣어둔다. 그리고 ) 괄호이면, 짝을 하나 찾은 것이므로 스택에서 가장 마지막에 들어간 ( 을 빼주면 된다 = pop으로 가장 마지막 요소가 삭제된다.
그런데 여기서 주의할 점은, 스택이 만약 비어있었다면, 이전에 열린괄호 (가 없었다는 뜻이기 때문에, 규칙을 위반한 것이다. 따라서 이런 경우에는 바로 false를 리턴하도록 한다.
s 문자열을 다 순회하였는데, 스택이 비어있지 않다면?
스택이 비어있지 않다는 건, 이전에 들어왔던 열린 괄호 개수만큼 짝이 될 닫힌 괄호가 없었다는 뜻과 같기 때문에, 이 경우에도 false를 리턴해야 한다.
따라서 결과가 true가 되려면, string 순회 후에 스택이 비어있어야 함을 알 수 있다.
위를 바탕으로 코드를 짜면 아래와 같다.
import java.util.Stack;
class Solution {
boolean solution(String s) {
boolean answer = true;
Stack<String> st = new Stack<>();
for(int i=0; i<s.length(); i++){
if(s.charAt(i) == '('){
st.push("(");
}else{
if(st.isEmpty()){
return false;
}else{
st.pop();
}
}
}
if(!st.isEmpty()) answer = false;
return answer;
}
}
<자바 문법>
** Stack을 사용하려면 java.util.Stack을 import 해야함.
** 문자열의 특정 위치의 문자에 접근하려면, s.charAt(인덱스) 를 사용하여 접근해야함.
** 문자의 경우 ' ', 문자열의 경우 " " 임을 명심하자.
'CO-TE > 프로그래머스' 카테고리의 다른 글
[프로그래머스] JAVA LV2 "더 맵게" 풀이방법 / 우선순위 큐 - min heap 사용 (0) | 2023.10.20 |
---|---|
[프로그래머스] JAVA LV2 "소수 찾기" 풀이 방법 / set 자료구조 사용 (0) | 2023.10.20 |
[프로그래머스] JAVA LV2 "가장 큰 수" 풀이 방법 / Arrays.sort / 람다식 사용 (1) | 2023.10.19 |
[프로그래머스] MYSQL LV3 조건에 맞는 사용자와 총 거래금액 조회하기 / GROUP BY 이용 (0) | 2023.10.19 |
[프로그래머스] MYSQL LV2 가격이 제일 비싼 식품의 정보 출력하기 / MAX와 서브쿼리 (0) | 2023.10.19 |