25. Baekjoon Gold5 2493. '탑'

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

2493번: 탑

처음에는 배열과 while문을 사용해서 이전 탑 높이에 따라 조건처리를 해주는 방식으로 풀었다.

그런데 채점 결과 시간초과가 나왔다.

 

- 시도 1

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

public class Q2493_탑_gold5 {
    // 6,9,5,7,4
    // 왼쪽 <-으로 발사
    // 어느 탑에서 수신하는지
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Scanner in = new Scanner(System.in);
        Stack<Integer> number = new Stack<>();
        Stack<Integer> index = new Stack<>();
        int N = Integer.parseInt(st.nextToken());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st2.nextToken());// 6
        number.push(n);// 1
        index.push(1);
        sb.append(0 + " ");

        for (int i = 2; i <= N; i++) {
            int val = Integer.parseInt(st2.nextToken());// 4
            while (!number.isEmpty()) {
                if (val < number.peek()) {
                    sb.append(index.peek() + " ");
                    break;
                }
                number.pop(); // 어차피 더 큰 탑이 오른쪽에 존재 = 왼쪽 작은탑은 pop해도 무방함.
                index.pop();
            }
            if (number.isEmpty()) {
                sb.append(0 + " ");
            }
            number.push(val);// 9 7 (여기서 꺼냄)
            index.push(i);// 2 4
        }
        System.out.println(sb.toString());
    }
}

 

두번째 시도 방법은 스택 사용!

비교 탑보다 큰 숫자들만 있는 스택, 그리고 인덱스 스택 두개를 만들어 준 후 

왼쪽에 위치하는 작은 탑은 pop() 하는 방식으로 순서대로 인덱스를 찾아주었다.

 

- 시도 2

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

public class Q2493_탑_gold5 {
    // 6,9,5,7,4
    // 왼쪽 <-으로 발사
    // 어느 탑에서 수신하는지
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Scanner in = new Scanner(System.in);
        Stack<Integer> number = new Stack<>();
        Stack<Integer> index = new Stack<>();
        int N = Integer.parseInt(st.nextToken());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st2.nextToken());// 6
        number.push(n);// 1
        index.push(1);
        sb.append(0 + " ");

        for (int i = 2; i <= N; i++) {
            int val = Integer.parseInt(st2.nextToken());// 4
            while (!number.isEmpty()) {
                if (val < number.peek()) {
                    sb.append(index.peek() + " ");
                    break;
                }
                number.pop(); // 어차피 더 큰 탑이 오른쪽에 존재 = 왼쪽 작은탑은 pop해도 무방함.
                index.pop();
            }
            if (number.isEmpty()) {
                sb.append(0 + " ");
            }
            number.push(val);// 9 7 (여기서 꺼냄)
            index.push(i);// 2 4
        }
        System.out.println(sb.toString());
    }
}

통과!