[백준] 1431 - 시리얼 번호(JAVA)

[백준] 1431 - 시리얼 번호

사실 이 문제는 많이 까다롭거나 어려운 문제는 아니었는데 내 실수로 헤맸었던 문제이다. 문제 자체는 문자열을 정렬하기 위한 comparator를 구현하면 되는 것이었는데, 내가 정렬 기준을 세울 때 잘못 생각한 부분이 있었다.

먼저 문제의 요구 조건
1.A와 B의 길이가 다르면, 짧은 것이 먼저 온다.
2.만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)
3. 만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다.
중에 2번이 문제였는데... 나는 각 자리수의 '합'을 구해서 비교하는 것이므로 실제값이 아닌 아스키 문자 값으로 더해도 합의 크기를 비교하는 데에는 문제가 없을 것이라고 생각했다.
그래서 아래와 같이 구현했고 결과는...

실제로 테스트케이스는 모두 통과하는데 자꾸 제출하고 나면 거의 바로 틀렸습니다가 나오더라..^-ㅜ
결국 챗GPT의 도움을 받아서 반례 케이스를 얻을 수 있었다. 아스키 값의 합은 같지만 실제 숫자 값의 합은 다른 경우이다.

문자열 "39":
아스키 값 합: 51 + 57 = 108
숫자 값 합: 3 + 9 = 12

문자열 "48":
아스키 값 합: 52 + 56 = 108
숫자 값 합: 4 + 8 = 12

그래서 다시 아래처럼 -'0' 처리를 해줘서 실제 숫자값을 합하도록 수정했더니 통과했다.

그리고 아래는 전체 소스코드인데, 사전순으로 정렬하는 부분은 return a.compareTo(b); 로 String의 compareTo 메서드를 이용해도 동일한 결과가 나온다.

import java.io.*;
import java.util.Arrays;

// 1431 - 시리얼 번호
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        String[] arr = new String[N];
        for (int i = 0; i < N; i++) {
            arr[i] = br.readLine();
        }
        br.close();
        Arrays.sort(arr, (a, b) -> {
            if (a.length() != b.length()) {
                return a.length() - b.length();
            }

            int sumA = 0;
            int sumB = 0;
            for (int i = 0; i < a.length(); i++) {
                if(a.charAt(i) >= '0' && a.charAt(i) <= '9'){
                    sumA += a.charAt(i) - '0';
                }
            }
            for (int i = 0; i < b.length(); i++) {
                if(b.charAt(i) >= '0' && b.charAt(i) <= '9'){
                    sumB += b.charAt(i) - '0';
                }
            }
            if(sumA != sumB) return sumA - sumB;

            // 사전순 정렬
            for (int i = 0; i < a.length(); i++) {
                if(a.charAt(i) != b.charAt(i)) {
                    return a.charAt(i) - b.charAt(i);
                }
            }

            return 0;

        });

        for (int i = 0; i < arr.length; i++) {
            bw.write(arr[i]);
            bw.write("\n");
        }
        bw.close();
    }
}