[백준 알고리즘 - 1806] 부분합 + StringTokenizer 정리 - java

최근에 문제를 풀다가 아주 놀라운 경험을 했는데

바로 입력 방식만 바꿈으로써 실행 시간이 400ms나 줄었다는 것이다!

Scanner를 통해 입력을 처리한 코드

import java.util.Scanner;
class Main{
       public static void main(String[] args) {
          Scanner scan=new Scanner(System.in);
          int N=scan.nextInt();
          int M=scan.nextInt();
          
          int[] A=new int[N];
          for(int i=0; i<N; i++) {
        	  A[i]=scan.nextInt();
          }
          
          int left=0; int right=0;
          int size=N;
          
          int sum=A[left];
          int min=N+1;
          int length=right-left+1;
          while(left<=right && right < size) {
        	  if(sum>=M) {
        		  length=right-left+1;
        		  if(min > length)
        			  min=length;
        		  if(left+1 < size)
        			  sum-=A[left];
                  left++;
        		  continue;
        	  }
        	  if(sum < M) {
        		  if(right+1<size)
        			  sum+=A[right+1];
                  right++;
        		  continue;
        	  }
          }
          if(min==N+1)
        	  min=0;
          System.out.println(min);
          
          
     }
       
}

이 코드의 실행 결과는 672ms 이다. 

 그리고 이 코드는 BufferedReader와 StringTokenizer를 통해 입력을 처리한 코드

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


class Main{
       public static void main(String[] args) throws IOException {



  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer st = new StringTokenizer(br.readLine());
  		int N = Integer.parseInt(st.nextToken());
  		int M = Integer.parseInt(st.nextToken());
  		int[] A=new int[N];
  		
  		st = new StringTokenizer(br.readLine());
  		for (int i = 0; i < N; i++)
  			A[i] = Integer.parseInt(st.nextToken());
        int left=0; int right=0;
        int size=N;
          int sum=A[left];
          int min=N+1;
          int length=right-left+1;
          while(left<=right && right < size) {
        	  if(sum>=M) {
        		  length=right-left+1;
        		  if(min > length)
        			  min=length;
        		  if(left+1 < size)
        			  sum-=A[left];
                  left++;
        		  continue;
        	  }
        	  if(sum < M) {
        		  if(right+1<size)
        			  sum+=A[right+1];
                  right++;
        		  continue;
        	  }
          }
          if(min==N+1)
        	  min=0;
          System.out.println(min);
          
          
     }
       
}

실행 시간은 232ms이다. 

입력 방식만 바꿨을 뿐인데 무려 400ms나 단축한 것이다.

그래서 정리하는 StringTokenizer 클래스 

StringTokenizer

• 생성자: StringTokenizer(String str)

-> str을 인자로 받는다. 위 예제에서는 입력 받는 한 줄을 인자로 넣어주었다.

• 함수:

  • countTokens() : 토큰 개수 리턴

  • nextToken(): 다음 토큰 리턴, 이전 토큰 제거 -> 어떤 구분자로 나누어진 입력 라인을 하나하나 쪼갤 수 있다.

  • nextToken(String delim): delim을 구획문자로 변경 후 다음 토큰 리턴

  • hasMoreTokens(): true/false

구획문자를 설정해주지 않으면 기본으로 공백을 기준으로 나눈다.

공백을 기준으로 입력을 주는 문제에서 유용하게 쓰일 것 같다