2회 테코테코

 

[2024.09.22] 10:00 ~ 12:00

---

≣ 목차

---

요약

- stack 자료 구조의 push, pop 메서드를 이용해서 문제를 해결할 수 있다.

- deque 자료 구조를 이용해서 stack, queue 를 구현할 수 있다.

---

스택

첫 번째 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

접근 방법

1. 열린 괄호일 경우, stack 에 push 한다.

2. 닫힌 괄호일 경우, stack 에 있는 마지막 값을(peek) pop 해서 올바른 괄호로 판단한다.

3. stack 이 최종적으로 비어있을 경우 올바른 괄호고, 비어있지 않을 경우 올바르지 않은 괄호다.

고민 포인트

- 괄호를 짝지어서 올바른 괄호임을 확인하는 것이 키 포인트

최종 코드 및 회고

- stack 문제의 가장 기초적인 문제라고 생각하고, 쉽게 접근할 수 있는 문제였다고 생각한다.

import java.util.*;

class Solution {
    boolean solution(String s) {
        
        Stack<Character> stack = new Stack<>();
        
        for (char b : s.toCharArray()) {
            if (b == '(') {
                stack.push(b);
            } else {
                //비어있는 경우 pop 할 수 없다.
                if (stack.isEmpty()) return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

---

두 번째 문제

https://school.programmers.co.kr/learn/courses/30/lessons/76502

프로그래머스

접근 방법

1. deque 를 사용해서 괄호 데이터를 저장한다.

2. 주어진 괄호 데이터 길이만큼(s.length()) 반복문으로 접근해서 올바른 괄호인지 확인한다.

3. deque 에 있는 데이터를 토대로, stack 을 이용해서 짝지어지지 않는 괄호인 경우 push 하고, 짝지어지는 경우 pop 한다.

3-1. 마지막으로 stack 이 비어있는 경우, 최종 count(올바른 괄호 개수) 를 증가 시킨다.

4. 주어진 괄호를 회전 시킨다. (계속 반복하면서 올바른 괄호 개수를 확인함...)

고민 포인트

- 어떤 자료 구조를 사용해서 각 괄호 데이터에 접근할 것인가?

- 얼마나 반복하면서 확인할 것인가?

- 회전은 언제 진행해야 하고, count 개수는 언제 증가 시켜야 하는가?

최종 코드 및 회고

- Map 으로도 데이터를 저장해 보고, deque + stack 조합으로 문제를 풀고자 했으나 일부만 정답되는 문제가 발생했다.

- 내가 생각했던 접근 방법과 가장 유사한 답안을 참고하여 코드를 개선하였다.

- '}]()[{' 데이터의 경우 회전했을 때, '()[{}]', '[{}]()' 데이터로 총 2개의 올바른 괄호 개수를 얻을 수 있다.

import java.util.*;

class Solution {
    public int solution(String s) {
        //deque 초기 값 세팅
        Deque<Character> deque = new LinkedList<>();
        for (char c : s.toCharArray()) deque.add(c);
        
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            //stack이 비어있는 경우 올바른 괄호 문자열 개수 추가
            if (isCorrect(deque)) count++;
            deque.addLast(deque.removeFirst());
        }
        return count;
    }
    
    private boolean isCorrect(Deque<Character> deque) {
        
        Stack<Character> stack = new Stack<>();    
        for (char d : deque) {
            //stack이 비어있는 경우, 값을 넣는다.
            if (stack.isEmpty()) stack.push(d);
            //stack에 값이 있는 경우
            else {
                //올바른 괄호 문자열인지 확인한다.
                if (stack.peek() == '(' && d == ')') stack.pop();
                else if (stack.peek() == '[' && d == ']') stack.pop();
                else if (stack.peek() == '{' && d == '}') stack.pop();
                //일치하지 않으면 stack에 값을 넣는다.
                else stack.push(d);
            }
        }
        return stack.isEmpty();
    }
}