Stack을 구현하는 효율적인 알고리즘은 무엇입니까?

Question

문제가 생겼습니다. 푸시 및 팝 작업으로 스택을 구현해야합니다.

입력

입력 파이 르의 인터넷 RST 라인은 하나의 정수 N (1 <= N <= 10^6) 포함 - 테스트 케이스의 수.

다음 N 줄은 작업에 대해 알려줍니다. +은 밀기를 의미합니다. -은 팝을 의미합니다. 나는 팝 된 요소를 인쇄해야합니다.

Example 
Input  Output 
6 
+ 1  10 
+ 10  1234 
- 
+ 2 
+ 1234 
- 

가 나는 코드

public class Main { 
    public static void main(String[] args) throws FileNotFoundException { 
     Scanner sc = new Scanner(new File("stack.in")); 
     PrintWriter pw = new PrintWriter(new File("stack.out")); 
     int n=sc.nextInt(); 
     int[] stack = new int[n]; int i=0; 
     while(n-->0) { 
      String s = sc.next(); 
      if(s.equals("+")) { 
       stack[i++]=sc.nextInt(); 
      } else { 
       pw.println(stack[--i]); 
      } 
     }  
     sc.close(); pw.close(); 
    } 
} 

이 프로그램은 시간 제한이을 초과 저를주고 다음 작성했습니다. 이 문제를 해결하는 효율적인 알고리즘을 제안하십시오. 엄지 손가락의

Time limit: 2 seconds 
Memory limit: 256 megabytes 

Answer 1

규칙 : 당신이 경쟁 프로그래밍 스타일의 문제를 해결하고, 입력이 큰 경우 (예를 들어, 10^5 숫자 이상)의 Scanner가 너무 느립니다 각 입력 파일에 대해

.

BufferedReader 위의 StringTokenizer을 사용하면 입력 속도를 높일 수 있습니다.

은 다음과 같이 할 수 있습니다

class FastScanner { 
    private StringTokenizer tokenizer; 
    private BufferedReader reader; 

    public FastScanner(InputStream inputStream) { 
     reader = new BufferedReader(new InputStreamReader(inputStream)); 
    } 

    public String next() { 
     while (tokenizer == null || !tokenizer.hasMoreTokens()) { 
      String line; 
      try { 
       line = reader.readLine(); 
      } catch (IOException e) { 
       throw new RuntimeException(e); 
      } 
      if (line == null) 
       return null; 
      tokenizer = new StringTokenizer(line); 
     } 
     return tokenizer.nextToken(); 
    } 

    public int nextInt() { 
     return Integer.parseInt(next()); 
    } 
}