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");
                }
            }
        }
    }
    

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


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

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


    11년 전 link
  • imyoyo
    imyoyo

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

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

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


    11년 전 link
  • Being
    Being

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


    11년 전 link
  • imyoyo
    imyoyo

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


    11년 전 link
  • mechi
    mechi

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


    11년 전 link
  • JongMan
    JongMan

    @imyoyo, 우왕ㅋ굳ㅋ


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