[백준] Q2204 도비의 난독증 테스트 JAVA

https://www.acmicpc.net/problem/2204

2204번: 도비의 난독증 테스트

 

1. 문제의 유형 및 이해

구현, 정렬

대소문자를 구분하지 않고 사전순으로 가장 앞서는 단어를 정답으로 한다.

apPle Bat AnT가 주어질 때 Ant apPle Bat 순으로 정렬이 된다.

각 테스트 케이스마다 주어지는 단어 개수 N 는 1000이하이다.

각 단어는 길이가 최대 20인 단어가 주어지고, 대소문자 구분을 없앴을 때 같은 단어는 주어지지 않는다.

2. 문제 접근 방법

문제에서 주어진대로 그대로 구현하면 됩니다.

구현함에 있어서 주의해야할 점은 '대소문자를 구분하지 않고 사전순으로 가장 앞서는' 순서대로 정렬을 하는 것입니다.

대소문자 구분을 없앳을 때 같은 단어는 주어지지 않으므로 대문자 또는 소문자로 변환하고 정렬을 하면됩니다.

하지만, 답을 출력할 때는 단어의 원본상태를 그대로 출력해야 합니다.

 

여러가지 방법이 있을 수 있는데, Comparator 함수 안에서 대소문자 구분을 통해 정렬을 하도록 했습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;

/**
 * @문제번호 : Q2204
 * @문제이름 : 도비의 난독증 테스트
 * @난이도 : Silver V
 * @date : 2022-03-23 오후 3:41
 * @author : pcrmcw0486
 * @문제이해
 * 대소문자를 구분하지 않고 사전순으로 가장 앞서는지 맞추도록한다.
 * 대소문자를 마구섞어가며 단어들을 제시한다.
 * @알고리즘
 * 단순 구현, 소팅
 * @접근방법

*/
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N;
        while ((N = Integer.parseInt(br.readLine())) != 0) {
            ArrayList<String> data = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                String s = br.readLine();
                data.add(s);
            }
            data.sort(new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return o1.toLowerCase().compareTo(o2.toLowerCase());
                }
            });
            sb.append(data.get(0)).append('\n');
        }
        System.out.print(sb);
    }
}

 

3. 기타

1. 정렬을 통해서 모든 문자를 정렬하는 방법도 있을 수 있지만, 데이터를 받으면서 바로바로 비교를 하게되면 더욱 빠르게 정답을 찾을 수 있다. 데이터가 작아서 정렬하는데 시간이 크게 걸리지 않았지만, 데이터가 커질 경우 정답을 더욱 빠르게 찾기 위해 이 방법이 더욱 효과적일 수 있다. -> 필요한 부분에 집중하는 것이 더욱 좋을 수 있다.

 

2. toLowerCase() 또는 toUpperCase()를 이용하지 않고도 할 수 있다. String class의 기능 중에는 

   compareToIgnoreCase()가 존재한다. 그래서 data.sort(~~) 부분을 data.sort(String::compareToIgnoreCase)를 사용하여도 정답이 나온다. 하지만 시간이 조금 더 걸린다.

    /**
     * A Comparator that orders {@code String} objects as by
     * {@code compareToIgnoreCase}. This comparator is serializable.
     * <p>
     * Note that this Comparator does <em>not</em> take locale into account,
     * and will result in an unsatisfactory ordering for certain locales.
     * The {@link java.text.Collator} class provides locale-sensitive comparison.
     *
     * @see     java.text.Collator
     * @since   1.2
     */
    public static final Comparator<String> CASE_INSENSITIVE_ORDER
                                         = new CaseInsensitiveComparator();
    private static class CaseInsensitiveComparator
            implements Comparator<String>, java.io.Serializable {
        // use serialVersionUID from JDK 1.2.2 for interoperability
        private static final long serialVersionUID = 8575799808933029326L;

        public int compare(String s1, String s2) {
            byte v1[] = s1.value;
            byte v2[] = s2.value;
            byte coder = s1.coder();
            if (coder == s2.coder()) {
                return coder == LATIN1 ? StringLatin1.compareToCI(v1, v2)
                                       : StringUTF16.compareToCI(v1, v2);
            }
            return coder == LATIN1 ? StringLatin1.compareToCI_UTF16(v1, v2)
                                   : StringUTF16.compareToCI_Latin1(v1, v2);
        }

        /** Replaces the de-serialized object. */
        private Object readResolve() { return CASE_INSENSITIVE_ORDER; }
    }
    
    
    //===================
     public int compareToIgnoreCase(String str) {
        return CASE_INSENSITIVE_ORDER.compare(this, str);
    }

 description에 따르면, 해당 comparator는 String을 compareToIgnoreCase를 통해 순서를 정해준다고 하는데, 지역을 고려하지 않는다고 한다. 그래서 특정한 locale에서는 올바르지 않을 수 있다고 한다.

• String에서 lowerCase(Locale locale)와 같은 함수를 통해 String class는 region과 locale에 맞추어서 기능을 지원하고 있다는 것을 알 수 있다. locale을 넣지 않으면 실제로 Locale.getDefault()가 들어가는 것을 볼 수 있다.

public int compareToIgnoreCase(String str) {
    return CASE_INSENSITIVE_ORDER.compare(this, str);
}

본론으로 돌아와서, 비교할 때 편하게 구현할 수는 있겠지만, compareToIgnoreCase를 사용할 때, 연산이 더욱 많이 들어가서 실제로 시간이 조금 더 걸린다. 

실제로 선택된 임의의 구현체를 선택해서 보게되면,

선택된 comparator 중 compareToCI

upperCase를 통해 실제로 변환하여 비교하는 것을 볼 수 있다.

 

compareToIgnoreCase를 사용하면 136ms 가 나온다.

정리하자면,

• compareToIgnoreCase라는 기능을 제공하는 것을 알 수 있지만 비교하는 연산을 실제로 들여다 볼때, String class의 coder()를 비교하고 확인하여 실제로 선택할 comparator구현체를 선택하는데 시간이 걸리고 실제 구현체를 들여다 보았을 때 변환하고 확인하는 과정이 똑같이 존재하고 있어서 고려하여 사용하는 것이 좋겠다.