2493번: 탑(Java)

 

 이런 유형은 처음 봐서 푸는 데 조금 걸렸다. 처음엔 Stack의 get()을 써서 모든 값을 비교해 봤지만, 예상대로 시간초과가 났다.

 Stack의 get()을 쓰는 목적이 index를 얻는 것이라는 것을 생각해 보다가 int[2] 배열을 쓰면 index와 값을 동시에 저장할 수 있다는 생각을 했다.

 

 

//변수 선언
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
Stack<int[]> stack = new Stack<>();
int num[];
int n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());

 

 

 

 

 

 

 

 

변수를 전부 선언하고, for(int i = 0; i<n; i++) 을 통해 n만큼 반복한다.

반복 내용은 다음과 같다.

for(int i = 0; i<n; i++)
{
    num = new int[2];
    num[0] = Integer.parseInt(st.nextToken());
    num[1] = i;
    while(!stack.isEmpty() && stack.peek()[0] < num[0])
    {
        stack.pop();
    }
    sb.append(!stack.isEmpty() ? stack.peek()[1]+1 + " " : 0 + " ");
    stack.push(num);
}

1. num = new int[2], num[0]에 입력받은 값 대입, num[1]에 i 대입

2. Stack이 비거나 Stack.peek()[0]이 num[0]보다 커질 때까지 pop() 

 2번을 하면 입력받은 값 보다 큰 값이 나올 때까지 Stack의 Top부터 pop()을 할 수 있다. 최종적으로 자신보다 큰 값이 나올 때까지 Stack을 pop 하므로, 해당 값의 index를 얻을 수 있다. Stack이 빈 경우는 일단 반복문을 종료하고 3번에서 다룬다.

3. Stack이 비어있다면, Stack 안에 입력받은 값 보다 큰 값이 없었다는 것을 의미하는 것이므로, StringBuilder에 0을 더하고, Stack이 비어있지 않다면 Stack 안에 입력받은 값 보다 큰 값이 있고, 그 값이 Stack의 Top에 있다는 것을 의미하므로, StringBuilder에 stack.peek()[1]+1을 더한다(문제의 출력에서는 index를 1부터 시작하므로 + 1을 해 줘야 한다)

4. Stack에 num을 push 한다.

 

 

 

 

결과 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        Stack<int[]> stack = new Stack<>();
        int num[];
        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        for(int i = 0; i<n; i++)
        {
            num = new int[2];
            num[0] = Integer.parseInt(st.nextToken());
            num[1] = i;
            while(!stack.isEmpty() && stack.peek()[0] < num[0])
            {
                stack.pop();
            }
            sb.append(!stack.isEmpty() ? stack.peek()[1]+1 + " " : 0 + " ");
            stack.push(num);
        }
        System.out.println(sb);
    }
}