오답케이스를 찾고 싶습니다.

  • buksu112
    buksu112

    안녕하세요? 아래 '단짝문자열'문제를 해결하다 오답케이스를 찾지 못해 글을 남깁니다.

    알고리즘은
    1. 입력데이터를 0번 부터 전체길이-4까지 char를 비교해가며, 왼쪽 부분 문자열, 오른쪽 부분 문자열을 찾는다.
    (-4를 한 이유는 'aabb'유형이 최소길이의 단짝문자열을 가지는 String이라 생각해서 입니다.)
    2. 찾아진 단짝 문자열이 기존에 찾은 문자열보다 길면 subStr의 내용을 대체
    3. 동일 길이의 후보군들은 sorting으로 사전순 앞서는 단짝 문자열 정의
    4. sorting시 왼쪽 부분문자열, 오른쪽 부분문자열, 가운데 문자 순으로 비교

    입니다.

    문제 : ZZAKSTR

    테스트 데이터 :
    7
    aadaacaabaa
    bbebbdbbcaabbhaa
    aaa......a
    aaa......aba
    aaa......abb
    aaa......baa
    aaa......abbb
    (아래 5개 입력은 길이가 2000자입니다.)

    소스코드 :

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

public class Main {
    static int T;
    static char[] input;
    static String subStr[] = new String [4];

    public static int compare(int a, int b) {
        int i = 0;
        while(a+i < input.length
                && b+i < input.length
                && input[a+i] == input[b+i]) {
            i++;
        }

        return i;
    }

    public static void sort() {
        String a, b;
        int i, j;
        for(i = 0; i < 3; i++) {
            a = subStr[i].substring(0, subStr[i].length()>>1) 
                    + subStr[i].substring((subStr[i].length()>>1) +1) 
                    + subStr[i].charAt(subStr[i].length()>>1);
            for(j = i+1; j < 4; j++) {
                b = subStr[j].substring(0, subStr[j].length()>>1)
                        + subStr[j].substring((subStr[j].length()>>1) +1) 
                        + subStr[j].charAt(subStr[j].length()>>1);
                if(a.compareTo(b) == 0) {
                    subStr[j] = (char)('z' + 1) + "";
                }
                else if(a.compareTo(b) > 0) {
                    String temp = subStr[i];
                    subStr[i] = subStr[j];
                    subStr[j] = temp;
                }

            }
        }
    }

    public static void main(String[] args) {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        int i, k, l, inpLen, MaxL, lL, rL;
        boolean isFind;

        //startTime = System.nanoTime();

        try {
        T = Integer.parseInt(sc.readLine());

        for(i = 0; i < T; i++) {
            input = sc.readLine().toCharArray();


            inpLen = input.length;

            isFind = false;

            subStr[0] = (char)('z' + 1) + "";
            subStr[1] = (char)('z' + 1) + "";
            subStr[2] = (char)('z' + 1) + "";
            subStr[3] = (char)('z' + 1) + "";

            MaxL = 0;
            for(k = 0; k < inpLen-3; k++) {         // 문자열 쌍이 나올수 있는 최소 길이는 4(aabb형)
                for(l = k+1; l < inpLen-2; l++) {
                    if(input[k] == input[l]) {
                        lL = compare(k,l);
                        rL = compare(k + lL + 1, l + lL + 1);

                        if(lL == rL && input[k + lL] != input[l + lL]) {
                            if(!isFind) {
                                subStr[0] = new String(input, k, (lL<<1) + 1);  
                                subStr[1] = new String(input, l, (lL<<1) + 1);
                                isFind = true;
                                MaxL = lL;
                            }
                            else if(lL > MaxL) {
                                subStr[0] = new String(input, k, (lL<<1) + 1);
                                subStr[1] = new String(input, l, (lL<<1) + 1);
                                MaxL = lL;
                                subStr[2] = (char)('z' + 1) + "";
                                subStr[3] = (char)('z' + 1) + "";
                            }
                            else if(lL == MaxL) {
                                subStr[2] = new String(input, k, (lL<<1) + 1);
                                subStr[3] = new String(input, l, (lL<<1) + 1);
                                sort();
                            }
                        }
                    }
                }
            }

            sort();

            if(!isFind) {
                System.out.println("lonly island");
            }
            else {
                System.out.println(subStr[0] + " " + subStr[1]);
            }

        }
        } catch(IOException e) {
            System.out.println("");
        }
    }
}

    실행시간은 간신히 IN했는데, 오답이 나와서 오답케이스 찾는게 쉽지 않네요.
    도와주시면 감사하겠습니다.


    8년 전
0개의 댓글이 있습니다.

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