백준 9442 - Sort Me (정렬, 룩업테이블)

문제  : https://www.acmicpc.net/problem/9442

9442번: Sort Me

 

 

Note

Sort Me 문제는 정렬 문제이긴 한데 정렬을 하기위한 비교함수와 문자열 비교함수를 직접 구현해야만 하는 문제이다.
일반적으로 문자열을 오름차순으로 정렬하기 위해서 알파벳 순서 [a-z, A-Z] 대로 정렬되고 만약 prefix 문자열은 동일한데 문자의 길이가 다른경우 문자열 길이가 더 짧은게 앞에 나오도록 정렬하는것이 상식적인데 이 문제에서는 A-Z 순으로 정렬하지 않고 지정된 알파멧 순서대로 정렬을 해야만 한다.

ex) S= [ "ANTLER" , "ANY", "COW" , "HILL", "HOW", "HOWEVER", "WHATEVER", "ZONE"] 

이 문제를 풀기 위한 포인트는 기존의 A-Z 알파벳의 아스키값으로 비교하면 안되고 입력으로 주어진 알파벳 순서대로 값을 비교해야 한다는것이다. 

그래서 입력된 알파벳의 새로운 아스키값을 매칭하기위한 룩업테이블을 (lookup table)만들었다

int length = ALPHABET.length();
int lookUpTable[] = new int[length];
    for(int i = 0 ; i < length ; i++) {
    int index = ALPHABET.charAt(i) - 'A';
    lookUpTable[index] = i;
}

만약 UVWXYZNOPQRSTHIJKLMABCDEFG 로 입력이 주어진다면  룩업테이블은 다음과 같이 저장된다.

U는 LOOKUP TABLE[20 번째 인덱스]=값은 0로 매칭
V는 LOOKUP TABLE[21 번째 인덱스]=값은 1로 매칭
W는 LOOKUP TABLE[22 번째 인덱스]=값은 2로 매칭
X는 LOOKUP TABLE[23 번째 인덱스]=값은 3로 매칭
Y는 LOOKUP TABLE[24 번째 인덱스]=값은 4로 매칭
Z는 LOOKUP TABLE[25 번째 인덱스]=값은 5로 매칭
N는 LOOKUP TABLE[13 번째 인덱스]=값은 6로 매칭
O는 LOOKUP TABLE[14 번째 인덱스]=값은 7로 매칭
P는 LOOKUP TABLE[15 번째 인덱스]=값은 8로 매칭
Q는 LOOKUP TABLE[16 번째 인덱스]=값은 9로 매칭
R는 LOOKUP TABLE[17 번째 인덱스]=값은 10로 매칭
S는 LOOKUP TABLE[18 번째 인덱스]=값은 11로 매칭
T는 LOOKUP TABLE[19 번째 인덱스]=값은 12로 매칭
H는 LOOKUP TABLE[7 번째 인덱스]=값은 13로 매칭
I는 LOOKUP TABLE[8 번째 인덱스]=값은 14로 매칭
J는 LOOKUP TABLE[9 번째 인덱스]=값은 15로 매칭
K는 LOOKUP TABLE[10 번째 인덱스]=값은 16로 매칭
L는 LOOKUP TABLE[11 번째 인덱스]=값은 17로 매칭
M는 LOOKUP TABLE[12 번째 인덱스]=값은 18로 매칭
A는 LOOKUP TABLE[0 번째 인덱스]=값은 19로 매칭
B는 LOOKUP TABLE[1 번째 인덱스]=값은 20로 매칭
C는 LOOKUP TABLE[2 번째 인덱스]=값은 21로 매칭
D는 LOOKUP TABLE[3 번째 인덱스]=값은 22로 매칭
E는 LOOKUP TABLE[4 번째 인덱스]=값은 23로 매칭
F는 LOOKUP TABLE[5 번째 인덱스]=값은 24로 매칭
G는 LOOKUP TABLE[6 번째 인덱스]=값은 25로 매칭

즉 U의 문자가 가장 작고 G로 갈수록 점점 문자의 값이 커지는 구조이다.

그리고 "ANTLER" 문자열은 비교시  룩업테이블데 맞도록 A(=19)N(=6)T(=12)L(=17)E(=23)R(=10) 값으로 비교하는 문자열 비교함수를 만들면된다.

public static int compareTo(String value, String anotherString, int[] lookUpTable) {
        int len1 = value.length();
        int len2 = anotherString.length();
        int lim = Math.min(len1, len2);
 
 
        int k = 0;
        while (k < lim) {
            int c1 = lookUpTable[value.charAt(k) - 'A'];
            int c2 = lookUpTable[anotherString.charAt(k) - 'A'];
            if (c1 != c2) {
                return c1 - c2;
            }
            k++;
        }
        return len1 - len2;
    }

전체 구현 코드는 아래와 가다. 

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
 
 
public class Main {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String[] input = br.readLine().split(" ");
        int datasetNumber = Integer.parseInt(input[0]);
        int year = 1;
        while(datasetNumber != 0 ) {
 
            List<String> dataset = new ArrayList<>(datasetNumber);
            for(int i = 0 ; i < datasetNumber ; i++) {
                dataset.add(br.readLine());
            }
 
            String ALPHABET = input[1];
            // 원래 A,B,C,D 순서로 정렬해야할 것을 입력된 알파벳 순서로 정렬하기위해
            // LOOK-UP 테이블을 만든다.
            int length = ALPHABET.length();
            int lookUpTable[] = new int[length];
            for(int i = 0 ; i < length ; i++) {
                int index = ALPHABET.charAt(i) - 'A';
                lookUpTable[index] = i;
            }
 
 
            // 원래 알파벳 순서가 아닌 룩업데이트에 정의된 순서대로 정렬한다.
            System.out.println(String.format("year %d", year));
            dataset.stream().sorted((a, b) -> compareTo(a, b, lookUpTable))
                    .forEach(System.out::println);
 
            input = br.readLine().split(" ");
            datasetNumber = Integer.parseInt(input[0]);
            year++;
        }
 
 
    }
 
 
    public static int compareTo(String value, String anotherString, int[] lookUpTable) {
        int len1 = value.length();
        int len2 = anotherString.length();
        int lim = Math.min(len1, len2);
 
 
        int k = 0;
        while (k < lim) {
            int c1 = lookUpTable[value.charAt(k) - 'A'];
            int c2 = lookUpTable[anotherString.charAt(k) - 'A'];
            if (c1 != c2) {
                return c1 - c2;
            }
            k++;
        }
        return len1 - len2;
    }
 
}