JAEHASAFE java 수행속도 향상 관련

  • bluenak
    bluenak

    JAEHASAFE 문제에 대한 질문 드립니다.
    Java를 이용해서 다음과 같이 구현하였고, 예제 TC 수행 결과는 정상적으로 출력됨을 확인하였습니다.

    다만 정답을 제출하고 나면 1000ms 내에 TC 수행에 실패해서 정답처리가 되지 않습니다.

    정답 통계를 보니 모든분들이 C++을 이용해서 구현을 하였더군요.
    아래의 코드에서 좀더 TC 수행 속도를 향상시킬만한 팁이 있을지 조언 부탁드립니다.

    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException { 
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int tc=0; tc<T; tc++){
            int number = Integer.parseInt(br.readLine());

            String line = br.readLine();
            char[] charArr = new char[line.length()];

            int cnt = 0;

            for(int i=0; i<line.length(); i++){
                charArr[i] = line.charAt(i);
            }

            for(int i=1; i<=number; i++) {
                String line2 = br.readLine();
                char[] charArr2 = new char[line2.length()];

                for(int j=0; j<line2.length(); j++){
                    charArr2[j] = line2.charAt(j);
                }

                if(i%2==0){
                    while(true){
                        int matchNum = 0;
                        for(int j=0; j<charArr.length; j++){
                            if(charArr[j] == charArr2[j]){
                                matchNum++;
                            } else {
                                break;
                            }
                        }

                        if(matchNum==charArr.length){
                            break;
                        }

                        char removed = charArr[0];
                        for(int j=1; j<charArr.length; j++){
                            charArr[j-1] = charArr[j];
                        }
                        charArr[charArr.length-1] = removed;

                        cnt++;
                    }
                } else {
                    while(true){
                        int matchNum = 0;
                        for(int j=0; j<charArr.length; j++){
                            if(charArr[j] == charArr2[j]){
                                matchNum++;
                            } else {
                                break;
                            }
                        }

                        if(matchNum==charArr.length) {
                            break;
                        }

                        char removed = charArr[charArr.length-1];
                        for(int j=charArr.length-1; j>0; j--){
                            charArr[j] = charArr[j-1];
                        }

                        charArr[0] = removed;
                        cnt++;
                    }
                }               
                charArr = charArr2;
            }

            System.out.println(cnt);
        }
    }
}

    9년 전
1개의 댓글이 있습니다.
  • Being
    Being

    수행 시간 순으로 정렬해 보시면 아시겠지만, 개선된 알고리즘을 통해 계산 복잡도의 차수를 줄이는 방법이 있습니다. 자바 등 다른 언어들이 성능으로 인해 불이익을 받는 부분에 대해서는 인지하고 있으며 언젠가(?) 수정될 지도 모릅니다. ㅠㅠ


    9년 전 link

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