프로그래머스 - 괄호 회전하기
본 포스팅은 java로 작성되었습니다.
이 문제는 프로그래머스 - 올바른 괄호 문제에서 다뤘던 문제와 유사한 점을 찾을 수 있었다.
'괄호 닫기'와 같은 문제는 닫히는 괄호가 나왔을 때, 열린 괄호의 위치가 중요하다는 것을 깨달았다.
해당 문제는 내 힘으로 풀지 못하고 책을 참고해서 풀었다.
1. 접근 방법
-
(), {}, [] 의 3가지 괄호 종류가 나오고 있다. 종류가 픽스되어있기 때문에 해당 값들을 가지고 있는 HashMap을 만들어준다. 괄호 종류에 따라 하나씩 무언가를 만들어 줄 필요가 없고 key-value를 갖는 HashMap을 사용하는 것이 이 문제의 중요한 접근법중 하나였던 것 같다.
-
핵심 로직
if ) 닫는 괄호일 경우 (), ], }):
스택이 비었으면 짝이 안 맞으므로 실패 → continue loop
스택이 비어있지 않으면 -> 스택에서 pop() → 짝이 맞는지 비교 (그때 hashmap에서 꺼내서 짝이 맞는지를 확인할 수 있음!! 일일히 어떤 괄호인지 체크하고 그 괄호에 맞는 여는 괄호인지 검증해주는 로직이 없어도 된다는 점)else) 여는 괄호일 경우 push
2. 최종 코드
import java.util.ArrayDeque;
import java.util.HashMap;
class Solution {
public int solution(String s) {
int answer = 0;
HashMap<Character, Character> map = new HashMap<>();
map.put(')', '(');
map.put('}', '{');
map.put(']', '[');
int length = s.length();
s += s;
loop:
for (int i = 0; i < length; i++) {
ArrayDeque<Character> stack = new ArrayDeque<>();
for (int j = i; j < i + length; j++) {
char c = s.charAt(j);
if (map.containsKey(c)) {
if (stack.isEmpty()) {
continue loop;
}
char top = stack.pop();
if (top != map.get(c)) {
continue loop;
}
} else {
stack.push(c);
}
}
if (stack.isEmpty()) {
answer++;
}
}
return answer;
}
}
3. Stack과 ArrayDeque의 차이
올바른 괄호 문제에서만 해도 Stack을 썼었다. 근데 언제부턴가 ArrayDeque를 쓰게 됐다.
그 이유는 간단하다. Stack은 오래된 클래스이고 성능도 좋지 않기 때문이다.
자바의 Stack 클래스는 내부적으로 Vector를 상속하고 있어, 모든 메서드가 동기화되어 있다. 즉, 멀티스레드 환경에서는 안전하지만, 단일 스레드 환경에서는 불필요한 비용이 발생한다. 그래서 알고리즘 문제처럼 빠르게 실행되는 게 중요한 상황에서는 적합하지 않다고 한다.
반면 ArrayDeque는 Deque 인터페이스를 구현한 스택과 큐의 기능을 모두 지원한다. 동기화가 필요 없는 환경에서는 훨씬 빠르고, 메모리 사용 면에서도 더 효율적이다.
4. Labeled Loop
처음엔 중첩 반복문 안에서 continue를 써야 할 때, 바깥 루프로 빠져나가려면 별도의 flag 변수를 만들어서 처리해야 했다.
예를 들어 괄호 검증 문제처럼, 한 번이라도 짝이 안 맞으면 바로 다음 회전으로 넘어가고 싶은데, Java에서는 일반적으로 continue가 가장 가까운 반복문만 제어할 수 있기 때문에 이중 for문 구조에서는 불편함이 있었다.
자바에서는 반복문 앞에 라벨(label)을 붙여두고, continue나 break 뒤에 해당 라벨을 지정하면 명시적으로 바깥 루프를 제어할 수 있다.
