[JAVA] 스택(Stack) / 카카오 크레인 인형 뽑기(KAKAO)

1. 스택(Stack) 이란 ?

스택은 "쌓다"라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조입니다.

스택은 후입선출(Last-In First Out:LIFO)의 형태로 일어나는 자료구조를 말합니다. 후입선출 구조란 예를 들어 스택에 A, B, C, D의 순서로 입력을 하여 스택에 넣었다면 D, C, B, A의 순서로만 꺼낼 수 있습니다.

Stack ADT(추상 데이터 타입)

Stack() : 비어 있는 새로운 스택을 만든다. 
isEmpty() : 스택이 비어있으면 true , 아니면 false를 반환한다.
push(e) : 항목 e를 스택의 맨 위에 추가한다.
pop() : 스택의 맨 위에 있는 항목을 꺼내어 반환한다. 
peek() : 스택의 맨 위에 있는 항복을 삭제하지 않고 반환한다. 
size() : 스택 내의 모든 항목들의 개수를 반환한다.
clear() : 스택을 공백상태로 만든다. 

2. 스택(Stack)은 어디에 사용?

스택은 특히 자료의 출력순서가 입력의 역순으로 이루어져야 할 경우에 매우 긴요하게 사용이 됩니다.

• 문서나 그림, 수식 등의 편집기에서 되돌리기(undo) 기능을 구현할 때 스택이 사용됩니다. 되돌리기는 지금까지 실행된 명령어 중에서 가장 최근 것부터 순서적으로 취소해야 하기 때문입니다. ( 웹 브라우저의 "이전 페이지로 이동" 기능 )
• 함수 호출에서 복귀주소를 기억하는데 스택을 사용
• 후위 표기법 계산

3. 스택(Stack)의 장/단점?

아직 큐에 대해 다루진 않았지만, 큐와 비교했을 때 스택의 장단점은 어떤 것들이 있는지 알아보았다!

<장점>
1. 단순한 구조
스택은 후입선출(LIFO, Last-In-First-Out)의 구조로, 데이터의 삽입과 삭제가 맨 위에서만 일어나기 때문에 구현이 단순합니다.

2. 실행 시간
스택의 삽입과 삭제 연산은 일반적으로 상수 시간인 O(1)에 이루어집니다.
함수 호출/반환 관리: 스택은 컴퓨터 프로그램에서 함수 호출과 반환을 관리하는 데 사용되며, 이러한 관리가 필요한 경우에는 큐보다 스택이 더 효과적입니다.

<단점>
1. 데이터 액세스 제한
스택에서는 맨 위에 있는 데이터에만 직접 액세스 할 수 있으므로, 중간에 있는 데이터에 접근하려면 그 이전의 모든 데이터를 삭제해야 합니다.

2. 크기 제한
스택의 크기가 제한되어 있으면, 스택 오버플로 문제가 발생할 수 있습니다.

 

---

.

먼저 스택을 공부하면서, 반드시 알아야 할 것 같은 부분을 문제풀이를 통해 알아보았다.

<문제>
입력된 문자열에서 소괄호 ( ) 사이에 존재하는 모든 문자를 제거하고 남은 문자만 출력하는 프로그램을 작성하세요.

<입력>
첫 줄에 문자열이 주어진다. 문자열의 길이는 100을 넘지 않는다.
ex) ((bf))ab

<출력>
남은 문자만 출력한다.
ex) ab

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String input = bf.readLine();
        Stack<Character> stack = new Stack<>();
        String answer = "";
        for(char x : input.toCharArray()) {
            if(x == ')') {
            // pop()은 꺼내기도 하지만, 꺼낸값을 리턴도 한다. 
                while(stack.pop() != '(');
            }
            else {
                stack.push(x);
            }
        }
        for(int i=0; i<stack.size(); i++) {
            answer += stack.get(i);
        }
        System.out.println(answer);
    }
}

위의 문제는 스택의 push() , pop()의 개념을 잘 공부해 볼 수 있는 문제였습니다.
만약 입력받은 문자열이 " ( ( b f ) ) a b "라고 한다면 , ()와 () 안의 문자를 제외한 문자들이 출력되는 문제입니다.
앞의 ( ( b f ) )까지 보았을 때, 첫 번째 ')'를 만나면서 if문이 만족하게 되고, 계속 pop()을 하다가 앞에서 두 번째 '('를 pop() 하면서 while문을 빠져나오게 됩니다.
이는 pop()이 "스택의 항목을 꺼내면서 그 값을 반환도 할 수있다"라는 성질을 이용한 부분입니다.

---

.

📖 문제

✅ KAKAO-크레인인형뽑기(2019)
.
.
게임개발자인 "죠르디"는 크레인 인형 뽑기 기계를 모바일 게임으로 만들려고 합니다.
"죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

크레인 작동 시 인형이 집어 지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다.

또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때,

크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 구하는 프로그램을 작성하세요.
( 인프런에서 문제를 참고하여 약간 다를 수 있음 ) 

💻 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        Stack<Integer> stack = new Stack<>();
        int N = Integer.parseInt(bf.readLine());
        int[][] A = new int[N][N];      // N x N 크기의 배열 생성
        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            for(int j=0; j<N; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int M = Integer.parseInt(bf.readLine());
        int[] moves = new int[M];
        StringTokenizer st = new StringTokenizer(bf.readLine());
        for(int i=0; i<M; i++) {
            moves[i] = Integer.parseInt(st.nextToken());
        }
        int answer = 0;
        for(int pos : moves) {
            for(int i=0; i<A.length; i++) {
                if(A[i][pos-1] != 0) {
                    int box = A[i][pos-1];
                    A[i][pos-1] = 0;
                    if(!stack.isEmpty() && box == stack.peek() ) {
                        answer += 2;
                        stack.pop();
                    } else {
                        stack.push(box);
                    }
                    break;
                }
            }
        }
        System.out.println(answer);
    }
}

🤯 내가 문제를 풀면서 어려웠던 부분

if(A[i][pos-1] != 0) {
     int box = A[i][pos-1];
     A[i][pos-1] = 0;
     if(!stack.isEmpty() && box == stack.peek() ) {
        answer += 2;		
        stack.pop();
     } else {
         stack.push(box);
      }
      break;
  }

어떤 식으로 N x N 배열에서 원소들을 탐색할 수 있을지 접근하기가 어려웠는데, moves를 pos로 받아 [pos-1]을 하여 A 배열에 접근할 수 있도록 하였다. 또한 , 처음에 먼저 pop()을 하고 answer을 증가시킨다던지와 같은 몇몇 실수들을 많이 했는데..  문제를 많이 풀어보면서 크고 작은 실수들을 줄여나가야겠다.