[백준] 20210번 파일 탐색기 (Java)

20210번 파일 탐색기

 

문자열 유형을 혼내주고 있는 도중 내가 혼나버렸다.

문제를 골랐는데, 항상 정답률을 보고 적당한 문제들을 골랐었는데 하하 왜 안 보고 골랐을까.

일단 골라버렸고, 코드는 작성해버렸고 문제를 풀었다.

 

---

1. 문제 분석

---

문제를 처음 보고나서 조건이 되게 많다는 것을 느꼈다.

얼핏 보기에는 뭔가 간단하게 그냥 조건 따라서 정렬하면 되는 문제라고 판단됐다. 그래서 선택했을지도...

 

1. 둘 다 숫자인 경우
2. 둘 중 하나만 숫자인 경우
3. 둘 다 숫자가 아닌 경우

크게 이렇게 3가지 경우로 나눌 수 있었다.

 

1. 둘 다 숫자라면?
   • 십진법으로 두 숫자의 크기를 비교한다.
   • 더 작은 숫자가 우선순위가 더 높다.
   • 만약 두 숫자의 크기가 같다면, 앞에 0의 개수가 적은 것이 우선순위가 더 높다.
   • 두 숫자의 크기도 같고, 앞에 0의 개수도 동일하다면 우선순위가 동일하다. (저는 여기서...시간낭비를...)
2. 둘 중 하나만 숫자라면?
   • 숫자가 문자보다 우선순위가 높다.
3. 둘 다 문자라면?
   • 문자의 우선순위는 다음과 같은 우선순위를 갖는다.
   • 두 문자가 같으면(A와 A) 우선순위가 동일하다.
   • 두 문자의 종류가 같으면(A와 a) 대문자가 우선순위가 높다.
   • 두 문자의 종류가 다르면(A와 c) AaBbCcDd....XxYyZz와 같은 우선순위를 갖는다. (문제 제대로 안 읽으면 여기서 고생)

또 고려해야 할 것이 있다. 이어져있는 숫자를 하나의 문자열로 사용을 하는데, 주어지는 숫자는 2^63을 초과할 수 있기 때문에 일반적인 Long 타입은 사용할 수 없다.

 

문제를 다 풀고 나서 다른 분들의 답을 봤는데, 반복문과 Index를 아주 매력적으로 사용해서 푸신 분들을 많이 봤는데... 존경스럽다.

나는 아주 큰 수도 저장할 수 있는 Java의 BigDecimal을 사용했다.

 

왜냐! BigDecimal은 Comparable 인터페이스를 구현하고 있어서 compareTo를 사용할 수 있기 때문에 사용해 봤다.

 

 

 

2. 소스코드

---

import java.io.*;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(reader.readLine());
        PriorityQueue<Value> queue = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            queue.add(new Value(reader.readLine()));
        }

        StringBuilder builder = new StringBuilder();
        while (!queue.isEmpty()) {
            builder.append(queue.poll()).append("\n");
        }
        System.out.println(builder);
    }
}

class Value implements Comparable<Value> {
    String value;
    ArrayList<String> seperatedValue;

    public Value(String value) {
        this.value = value;
        setSeperatedValue(value);
    }

    private void setSeperatedValue(String value) {
        this.seperatedValue = new ArrayList<>();
        StringBuilder tempBuilder = new StringBuilder();

        for (int i = 0; i < value.length(); i++) {
            char temp = value.charAt(i);

            if (Character.isDigit(temp)) {
                tempBuilder.append(temp);
                continue;
            } else if (tempBuilder.length() > 0) { // 숫자 아니고, 빌더에 값이 있는 경우
                seperatedValue.add(tempBuilder.toString());
                tempBuilder = new StringBuilder();
            }
            seperatedValue.add(String.valueOf(temp));
        }

        if (tempBuilder.length() > 0) { // 다 돌고 빌더에 남아 있는 것이 있으면 마저 넣어줌
            seperatedValue.add(tempBuilder.toString());
        }
    }

    @Override
    public int compareTo(Value other) {
        ArrayList<String> seperatedValueOfOther = other.seperatedValue;
        int smallSize = Math.min(seperatedValueOfOther.size(), this.seperatedValue.size());
        for (int i = 0; i < smallSize; i++) {
            String valueOfThis = this.seperatedValue.get(i);
            String valueOfOther = seperatedValueOfOther.get(i);

            boolean isNumberOfThis = isNumber(valueOfThis);
            boolean isNumberOfOther = isNumber(valueOfOther);

            // 둘 다 숫자인 경우
            if (isNumberOfThis && isNumberOfOther) {
                BigDecimal decimalOfThis = convertToDecimal(valueOfThis);
                BigDecimal decimalOfOther = convertToDecimal(valueOfOther);

                if (decimalOfThis.equals(decimalOfOther)) {
                    // 값도 같고, 0의 개수도 같은 경우
                    if (valueOfThis.length() == valueOfOther.length()) {
                        continue;
                    }
                    return valueOfThis.length() - valueOfOther.length();
                }
                return decimalOfThis.compareTo(decimalOfOther);
            }

            // 둘 중 하나만 숫자인 경우
            if (isNumberOfThis || isNumberOfOther) {
                return isNumberOfThis ? -1 : 1;
            }

            // 둘 다 문자인 경우
            int comparedValue = compare(valueOfThis, valueOfOther);

            if (comparedValue == 0) {
                continue;
            }

            return comparedValue;
        }

        return this.value.length() - other.value.length();
    }

    private int compare(String value1, String value2) {
        if (value1.equals(value2)) {
            return 0;
        }
        if (value1.equalsIgnoreCase(value2)) {
            if (value1.toUpperCase().compareTo(value1) == 0) {
                return -1;
            }
            return 1;
        }

        return value1.compareToIgnoreCase(value2);
    }

    private boolean isNumber(String value) {
        return Character.isDigit(value.charAt(0));
    }

    private BigDecimal convertToDecimal(String value) {
        return new BigDecimal(value);
    }

    @Override
    public String toString() {
        return value;
    }
}

 

처음에 BigDecimal의 생성자를 무자비하게 그냥 사용했었는데, 속도가 많이 떨어지는 것을 느꼈다.

 

그래서 isNumber()라는 메서드를 분리해서 해당 문자열이 숫자인지 확인한 후에 숫자인 경우에만 BigDecimal을 사용하도록 변경했더니 속도가 어느 정도 개선은 됐다.

 

그래도 확실히 속도는 조금 떨어지는 것 같아 보이기는 했다. 집념으로... 풀어서 그래도 오늘 문제 해결해서 잠들 수는 있을 거 같다.

 

집념의 흔적....isNumber()를 적용한 후에 1848ms에서 1384ms까지 속도가 올라가는 것을 확인할 수 있었다.