[자바] 백준: 2493 탑

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

2493번: 탑

 

---

처음 작성했던 코드(실패)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.Vector;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		Vector<Integer> v = new Vector<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			v.add(Integer.parseInt(st.nextToken()));
		}

		System.out.print(0 + " ");
		for (int i = 1; i < n; i++) {

			for (int j = i - 1; j >= 0; j--) {
				if (v.get(i) < v.get(j)) {
					System.out.print(j + 1 + " ");
					break;
				} else if (j == 0 && v.get(i) >= v.get(j)) {
					System.out.print(0 + " ");
				}
			}
		}

	}

}

매번 내 앞에있는 탑들을 전부 조사하는 방식이었다

탑의 최대 개수는 500,000개인데, 이 방식으로 하면.. 시간복잡도가 O(n^2)정도 될 듯하다.

 

그래서 다시 짠 코드

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

public class Main {

	static class Top{
		int height;
		int index;
		public Top(int height, int index) {
			this.height=height;
			this.index=index;
			
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		Stack<Top> stack = new Stack<>();
		
		int n = Integer.parseInt(br.readLine());
	
		int currentNum;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {

			currentNum=Integer.parseInt(st.nextToken());
			if(stack.isEmpty()) {//스택이 비었음
				System.out.print(0+" ");
				stack.push(new Top(currentNum,i+1));
			}
			else {//스택에 뭔가 있음
				if(stack.peek().height>currentNum) {//스택top의 높이가 현재것보다 높음
					System.out.print(stack.peek().index+" ");
					stack.push(new Top(currentNum,i+1));
				}
				else {//스택top의 높이가 현재것의 높이보다 작음
					while(!stack.isEmpty()&&stack.peek().height<=currentNum) {
						stack.pop();
					}
					if(stack.isEmpty()) {
						System.out.print(0+" ");
						stack.push(new Top(currentNum,i+1));
					}
					else {
						System.out.print(stack.peek().index+" ");
						stack.push(new Top(currentNum,i+1));
					}
				}
				
			}
		}

	}

}

스택을 이용했다.

 

1. 탑을 순서대로 스택에 넣는다.

2. 스택이 비었다면 0 출력 후 현재의 탑을 스택에 push한다.

3. 스택이 비어있지 않다면 TOS(top of stack)의 높이와, 현재것의 높이를 비교한다.

4. 현재것의 높이가 더 낮다면, TOS의 인덱스를 출력하고, 현재의것을 push한다.

5. 현재것의 높이가 더 크다면, TOS가 현재것보다 더 높은 탑이 되거나, 스택이 빌 때까지 스택pop 한다.

6. 이후 스택이 비었다면 0 출력 후 현재의 탑을 push함

7. 스택이 비지 않았다면 TOS의 인덱스를 출력하고 현재의 것을 push함.

---

자바에서 Scanner를 이용하면 값을 입력받는 데 시간이 오래걸린다고 한다.

더 빠르게 값을 입력받기 위해 BufferedReader를 이용하여 한 줄 입력을 받고, 

StringTokenizer를 이용하여 값들을 분할하였다.