[Algorithm] 스택과 큐 자료구조

`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다

 

✨ 개념

스택

- `선입후출` 또는 `LIFO` (Last In First Out)

- 먼저 들어온 데이터가 나중에 나가는 형식의 자료구조

- 파이썬 : 별도의 자료구조 없이 리스트를 사용 -> 리스트를 거꾸로 뒤집어 출력

- 자바 : Stack 자료구조 사용 -> push, pop, peek(출력) 메소드 사용

예시

- 박스 쌓기

- 가장 나중에 쌓은 박스부터 들어올려야 한다

- 배열 뒤집기 문제를 풀었는데 새로운 메소드를 알게 되어 추가

for (char c : str.toCharArray()) { }

 

- 문자열에서 하나씩 추출하며 반복(?) 할 때 이런 식으로 사용한다고 한다

Stack<Integer> q = new Stack<>();

// 삽입
q.push(5);

// 삭제 -> 꺼내고 바로 반환
q.pop();

// 출력
q.peek(); // -> 바로 나옴

 

큐

- `선입선출` 또는 `FIFO` (First In First Out)

- 먼저 들어온 데이터가 먼저 나가는 형식의 자료구조

- 파이썬 : 리스트도 가능하지만 deque 라이브러리가 더 효율적이다 -> append, popleft

    -> 오른쪽으로 들어와 왼쪽으로 나간다

- 자바 : Queue 자료구조 사용

예시

- 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화

Queue<Integer> q = new LinkedList<>();

// 삽입
q.offer(5);

// 삭제 -> 꺼내고 바로 반환
q.poll();

// 출력
q.poll(); // -> 바로 나옴

---

✨ 문제

10799번: 쇠막대기

---

✨ 접근

사진 출처 : https://gimbalja.tistory.com/401

 

- 강의에 나온대로 스택을 사용해서 풀었다

 

1. '('인 경우 push()

 

2. ')'인 경우 pop()

        -> '('과 ')'이 쌍이고 ')'이 스택에 먼저 등장할 리 없으므로

        -> pop할 때 ')'은 스택에 추가되지 않으므로 스택에서 제거되는 문자는 '('이다

 

2-2. 레이저인 경우 스택 길이만큼 더해주기 (사진 참조)

        => 들어온 원소가 ')'인 경우, 스택의 마지막 원소가 '('인 경우

        => 레이저가 들어올 때 스택의 원소 개수만큼 쇠막대기가 끊기므로 스택의 원소 개수만큼 더해줘야 한다

 

2-3. 레이저가 아닌 경우 return 값에 +1 해주기

        => 레이저가 아닌데 ')'이 나온 경우는 막대의 끝이 나오는 경우밖에 없으므로 하나의 막대만 끊긴다. 그러므로 +1을 해줘야 한다.

---

✨ 구현

- '('인 경우, ')'인 경우, 스택이 비어있는 경우, 레이저인 경우 등 여러 경우의 수를 생각해서 풀다가 너무 복잡해지고 시간 초과가 뜰 것 같아 다른 분들의 코드를 참고했다.

import java.io.*;
import java.util.Stack;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String input = br.readLine();
        Stack<Character> stack = new Stack<>();

        int result = 0;

        // 들어온 괄호의 개수만큼 for문 돌기
        for (int i=0; i<input.length(); i++) {
            // 괄호가 열려 있으면 스택 추가
            if (input.charAt(i) == '(') {
                stack.push('(');
                continue;
            }

            // 괄호가 닫혀 있을 경우 스택에서 '(' 꺼내기
            if (input.charAt(i) == ')') {
                stack.pop();

                // 바로 전 들어온 괄호가 열려 있으면 -> 레이저면
                if (input.charAt(i-1) == '(') {
                    result += stack.size(); // 현재 스택의 사이즈만큼 더해주기
                } else {
                    result ++;
                }
            }
        }

        bw.write(result + "\n");
        bw.flush();
        br.close();
        bw.close();
    }
}

---

✨ 참고 자료

https://steady-coding.tistory.com/10

https://gimbalja.tistory.com/401