2493 - Java

내코드

package com.hw;

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

public class BOJ2493 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		//idx, val
		Stack<int[]> stk = new Stack<>();
		
		for(int i=0;i<n; i++) {
			int num = Integer.parseInt(st.nextToken());
			
			while(!stk.isEmpty()) {
				if(stk.peek()[1] > num) {
					System.out.print(stk.peek()[0] + " ");
					break;
				}else {
					stk.pop();			
				}
			}
			if(stk.isEmpty()) {
				System.out.print("0 ");
			}
			stk.push(new int[] {i+1,num});
		}
	}

}

풀이

1. Scanner를 사용해서 처음엔 메모리 초과가 났다 => BufferedReader 사용
   
   Scanner가 편리하지만, 공백을 기준으로 하나하나 읽기 때문에 느릴 수 있다. 하지만 범용성에서는 좋음 . BufferedReader는 한줄을 통째로 읽는 방식으로 String값만 받아서 불편하지만 크기가 큰 상황에서는 .Scanner보다 빠르다... 속도면에서 약 8배차이

2. 풀이를 위해서 스택 사용
   stack문제에서 중요한 것은 push 와 pop 의 기준을 잡는 것
   이문제에서는 현재 타워가 top에 있는 타워보다 크다면 왼쪽에 잇는 타워로 절대 도달할 수 없으므로 자기보다 큰 값을 찾을때가지 pop()
   
   스택의 top값을 기준으로 현재 받는 값이 top보다 작으냐 크냐 기준으로 나누었다
   현재 값이 top보다 작으면 당연히 top에 있는 것의 인덱스를 출력
   -> 이를 위해 스택에 {idx,val} 구조로 저장
   현재 값이 top보다 크다면 현재 값보다 큰 값을 찾을때까지 stack.pop()
   그리고 무조건 현재 값을 stack 에 push한다