[BOJ - JAVA] 2493 - 탑 (스택)

# 주소

https://www.acmicpc.net/problem/2493

2493번: 탑

# 문제

# 문제 해설 및 코드리뷰

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

class Main{
    static int n;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> idx = new Stack<>();
        stack.push(Integer.parseInt(st.nextToken()));
        idx.push(1);
        sb.append("0");
        for(int i = 1; i < n; i++){
            int current = Integer.parseInt(st.nextToken());
            while(true){
                if(!stack.isEmpty()){
                    if(stack.peek() >= current){
                        sb.append(" ").append(idx.peek());
                        stack.push(current);
                        idx.push(i + 1);
                        break;
                    }else{
                        stack.pop();
                        idx.pop();
                    }
                }else{
                    sb.append(" 0");
                    stack.push(current);
                    idx.push(i + 1);
                    break;
                }
            }
        }
        System.out.println(sb);
    }
}

스택을 한 개만 선언하면 풀 수 없는 문제입니다. 

(만약 아신다면 댓글좀...)

그리고 N값이 크기 때문에 Scanner로 사용하면 시간초과 뜹니다.

그러므로 Buffer를 이용했습니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
arr = new int[n];
st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
Stack<Integer> stack = new Stack<>();
Stack<Integer> idx = new Stack<>();
stack.push(Integer.parseInt(st.nextToken()));

arr의 크기는 n으로 정하고 StringBuilder도 사용할 것이므로 sb로 선언합니다.

값을 담을 stack과 인덱스를 담을 idx를 선언합니다.

stack에는 제일 첫번째 입력값을 먼저 넣고

idx.push(1);
sb.append("0");

idx에는 1을 넣을 것입니다.

이유는 제일 처음 넣을 값과 인덱스가 1이고 arr[0]이기 때문이지요.

sb는 정답으로 출력할 것이기 때문에 최초의 정답은 0으로 시작합니다.

for(int i = 1; i < n; i++){
    int current = Integer.parseInt(st.nextToken());

i 는 1부터 시작하여 n까지 for문을 돌릴 것이고 입력받는 값을 current에 담아옵니다.

if(!stack.isEmpty()){
    if(stack.peek() >= current){
        sb.append(" ").append(idx.peek());
        stack.push(current);
        idx.push(i + 1);
        break;
    }else{
        stack.pop();
        idx.pop();
    }
}else{
    sb.append(" 0");
    stack.push(current);
    idx.push(i + 1);
    break;
}

그리고 stack이 비어있지 않을때와 비어있을 때를 분기하여 진행합니다.

만약 스택이 비어있지 않다면 스택의 peek와 입력받은 current를 비교를 할텐데요

만약 peek가 current보다 크거나 같으면 레이저를 쐈을 때 접해야 하는데 그렇지 않겠지요.

따라서 예제의 입력문이 6 9 5 7 4였듯이 9의 레이저는 어디에도 도달하지 못합니다.

그말인 즉슨 current가 stack보다 크다는 의미이므로 0을 출력하기 위해, stack과 idx를 모두 제거합니다.

따라서 stack과 idx는 빈 자료구조가 될 것이에요.

이후 다시 while문이 돌고 sb에는 0을 싣고 stack에는 current, idx에는 2를 싣고 break합니다.

이에 stack은 9가 담길테고 idx에는 2가 담기겠네요.

다시 while문으로 갑시다.

이제는 arr값이 5이므로 5는 9보다 작잖아요.

따라서 stack이 current보다 더 커지므로 sb에는 idx의 peek를 넣을 것입니다.

그 idx의 peek는 2였고 pop이 아닌, peek를 하는 이유는 그 다음 배열에서 또 쓸 수 있기 때문입니다.

이후 stack에도 current값을 넣고 idx에는 i + 1을 넣고 마찬가지로 break합니다.

쉽게 생각해보면 stack에는 어쨌든 current를 넣고 idx에는 어쨌든 i + 1을 넣는 것이 목표입니다.

그러나 stack.peek()보다 currnet가 더 크다면 stack과 idx값을 모두 제거하여 이것들의 값이 정답인 sb에 못담기게 해야 합니다.

따라서 pop을 하여 차례대로 제거하는 것이지요.

이 과정이 모두 끝난다면 sb에는 정답이 출력될 것입니다.

 

제일 처음 풀었을 때는 저는 이중 for문을 이용했습니다.

그런데 정답이 30%였나 까지 올라가고 시간초과가 뜨는거에요.

그래서 스택을 2개 사용하는 풀이를 익혔습니다.

 

감사합니다.