0-1 수열 문제를 풀고있는데요..

  • mechi
    mechi 
    import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String number = sc.next();
        int size = number.length();
        char[] numberArray = number.toCharArray();
        int[] checkArray = new int[size];

        int n = -1;
        int checkValue = -1;

        for(int i=0;i<size;i++){
            if(n!=numberArray[i]){
                checkValue++;
                n = numberArray[i];
            }
            checkArray[i] = checkValue;
        }
        int cases = sc.nextInt();       
        while(cases-- > 0) {
            int x = sc.nextInt();
            int y = sc.nextInt();

            if(checkArray[x] == checkArray[y]){
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
}

    요렇게 했는데.. 계속 시간초과가 나네요.. 어느 부분을 생각해야 해결이 될지 막막합니다... 조언 부탁드릴게요 ㅠ


    12년 전
6개의 댓글이 있습니다.
  • Being
    Being

    혹 http://algospot.com/forum/read/1364/ 이 도움이 될지 모르겠습니다.


    12년 전 link
  • imyoyo
    imyoyo

    좀전에 자바로 풀긴했는데 시간과의 사투끝에 턱걸이로 겨우 맞았습니다ㅠ

    일단 스캐너는 매우 느리니 다른 방법을 쓰시는게 좋을 것 같습니다. 저는 입력을 미리 모두 읽어서 StringTokenizer를 사용했습니다.
    그리고 이런 경우는 저도 처음인데, 출력만 빼고 서밋해본 결과 System.out.println으로 출력하는데 시간이 매우 많이 걸리더라고요. 출력을 모은 후 한꺼번에 출력하니 시간안에 아슬아슬하게 나왔습니다.

    사실 로컬에서 10만라인을 출력하는건 순식간이라 좀 이상하다는 생각이 듭니다. 혹시 자바저지환경의 IO가 느린게 아닐까요?


    12년 전 link
  • Being
    Being

    우와..... 대단하십니다 ㅠㅠ 대체로 IO가 좀 느린 영향이 있을 것 같고, println()하면 buffering을 안 할 것 같은 느낌이 드네요. 흠...


    12년 전 link
  • imyoyo
    imyoyo

    자바소스를 보니 println은 매번 flush 하네요~


    12년 전 link
  • mechi
    mechi

    답변 감사드립니다.. 참고해서 다시 해보겠습니다!!


    12년 전 link
  • JongMan
    JongMan

    @imyoyo, 우왕ㅋ굳ㅋ


    12년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.