글 읽기 - 예제, 반례는 다 맞는데 뭘 놓치고 있는지 잘 모르겠습니다

cos8475 2년 전 0

예제랑 올라온 반례는 다 맞는데 계속 틀립니다

코드를 계속 보고 있는데 뭐가 잘못된건지 잘 모르겠습니다 고수님들 도와주세요

import java.util.*;
import java.math.BigInteger;
import java.io.*;

class Main {

    public static void main(String[] args) throws java.lang.Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char A = 'A', a = 'a';
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < 52; i += 2) {
            map.put(A, i);
            map.put(a, i + 1);
            A++;
            a++;
        }
        //AaBbCcDd
        //01234567
        Comparator<String> comp = new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                char[] as = a.toCharArray(), bs = b.toCharArray();

                int len = 0;

                if (a.length() < b.length())
                    len = a.length();
                else
                    len = b.length();

                char ac, bc;
                for (int i = 0; i < len; i++) {
                    ac = as[i];
                    bc = bs[i];

                    // 둘다 문자라면
                    if (Character.isLetter(ac) && Character.isLetter(bc)) {
                        if (ac == bc)
                            continue;
                        // 같은 문자라면 continue;
                        return map.get(ac) - map.get(bc);
                    }

                    // 둘중 하나만 숫자라면 숫자 먼저
                    if (Character.isDigit(ac) && Character.isLetter(bc))
                        return -1;
                    if (Character.isLetter(ac) && Character.isDigit(bc))
                        return 1;

                    // 여기서 부턴 둘다 숫자
                    BigInteger along, blong;
                    String AZ, BZ;
                    int idx = i;
                    while (true) {
                        if (Character.isDigit(as[idx])) {
                            idx++;
                        } else {
                            break;
                        }
                        if (idx == a.length()) {
                            break;
                        }
                    }
                    AZ = a.substring(i, idx);
                    along = new BigInteger(AZ);

                    idx = i;
                    while (true) {
                        if (Character.isDigit(bs[idx])) {
                            idx++;
                        } else {
                            break;
                        }
                        if (idx == b.length()) {
                            break;
                        }
                    }
                    BZ = b.substring(i, idx);
                    blong = new BigInteger(BZ);

                    int result = along.compareTo(blong);

                    if (result == 0) {
                        if (along.intValue() + blong.intValue() == 0) {
                            return AZ.length() - BZ.length();
                            // 000, 00은 같은 값이다
                            // 이땐 길이로 계산한다
                        } else {
                            continue;
                            // 000,00이 아닌상황에서 같은 값이면 continue;
                        }
                    }
                    return result;
                }
                return a.length() - b.length();
            }
        };

        int k = Integer.parseInt(br.readLine());

        List<String> list = new ArrayList<>();
        for (int j = 0; j < k; j++)
            list.add(br.readLine());

        list.sort(comp);

        for (String s : list)
            System.out.println(s);

    }
}

slah007 2년 전 1

aa2147483648

aa0000000000000

둘 다 0인지를 intvalue로 변환한 후에 검사하는 것은 위험합니다.

cos8475 2년 전 0

조언대로 비교 방법을 변경했는데 계속 틀리네요ㅠㅠ. 여튼 알려주셔서 감사합니다

// 비교했을때 같다는건 123,123 또는 000,00이 될 수 있다
if (result == 0) {
  if (along.compareTo(new BigInteger("0")) == 0 && blong.compareTo(new BigInteger("0")) == 0) {
     if(AZ.length()==BZ.length()){
       continue;
     }
     return AZ.length() - BZ.length(); // 000,00 이라면 길이가 짧은걸 반환해야 한다
   }
   continue;
}

slah007 2년 전 1

사실 다른 문제점이 있는데 WA가 절대 안 난다고 생각해서 넘겼는데 고치고 내 보니까 AC가 나네요 진짜 왜지

결론은 result == 0이면 a=b=0이 아니더라도 앞의 0의 개수를 세 봐야 합니다. 길이가 완전히 같으면 continue 하고요

제 생각에는 지금 i를 무조건 1씩 증가시키고 있어서 둘 다 0이 아니라면 i가 커질 때 0이 더 많은 숫자가 결국 제일 먼저 첫 번째 자리가 잘리게 되어 큰 문제가 없는 것 같은데 아니네요;;

그리고 지금 코드는 시간 초과를 받기 쉬워 고치는게 좋습니다.

숫자를 비교한 뒤에는 i를 idx까지 당겨야 합니다. 그렇지 않으면 모든 문자열이 0의 개수를 제외하고 같은 긴 숫자일 때 50*50*10000 log 10000번의 연산이 필요하고 시간 초과를 야기할 수 있습니다.

cos8475 2년 전 0

slah007님 감사합니다. 덕분에 맞출 수 있었습니다. 👍👍👍

시간내주셔서 감사합니다 :D

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

예제, 반례는 다 맞는데 뭘 놓치고 있는지 잘 모르겠습니다

cos8475 2년 전 0

slah007 2년 전 1

cos8475 2년 전 0

slah007 2년 전 1

cos8475 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말