코드 한 줄

이 문제는 가장 긴 공통된 접두사가 첫 단어라고 가정하고, 각 문자마다 모든 단어에 비교한다.

비교하는 방식은 단어의 같은 위치에 문자가 있는지 확인한다.

만약 문자가 다르거나, 문자가 없으면 현재의 문자 위치까지만 공통된 접두사이다.

int longestPrefixLength(String[] arr) {
    if (arr.length == 0) {
        return 0;
    }
    String max_prefix = arr[0];
    for (int i = 0; i < max_prefix.length(); i++) {
        char c = max_prefix.charAt(i);
        for (int j = 1; j < arr.length; j++) {
            if (i == arr[j].length() || arr[j].charAt(i) != c) {
                return i;  
            }
        }
    }
    return max_prefix.length();
}

이 문제는 “Quick Select”의 알고리즘을 사용하는 대표적인 문제이다.

Quick select는 퀵 정렬(quick sort)를 이용하는 알고리즘이다.

퀵 정렬의 pivot을 정하고 1차 정렬을 하면 pivot의 원소 위치는 최종 정렬된 배열의 위치가 된다.

이것을 이용하여 모든 배열을 정렬 하지 않고, pivot의 값을 비교하여, 찾는 값에 따라 pivot의 왼쪽이나 오른쪽만 정렬하는 알고리즘이다.

int quickselect(int[] arr, int k) {
    return quickselect(arr, 0, arr.length - 1, k - 1);
}

int quickselect(int[] arr, int first, int last, int k) {
    if (first <= last) {
        int pivot = partition(arr, first, last);
        if (pivot == k) {
            return arr[k];
        }
        if (pivot > k) {
            return quickselect(arr, first, pivot - 1, k);
        }
        return quickselect(arr, pivot + 1, last, k);
    }
    return Integer.MIN_VALUE;
}

int partition(int[] arr, int first, int last) {
    int pivot_spot = first;
    for (int i = first; i < last; i++) {
        if (arr[i] > arr[last]) {
            swap(arr, i, pivot_spot);
            pivot_spot++;
        }
    }
    swap(arr, pivot_spot, last);
    return pivot_spot;
}

void swap(int[] arr, int x, int y) {
    int tmp = arr[x];
    arr[x] = arr[y];
    arr[y] = tmp;
}

이 문제는 긴 String 을 각 단어로 나눈 다음, 각 단어를 거꾸로 하고, 모든 단어들을 합치면 풀 수 있다.

public String reverseString(String s) {
    String words[] = split(s);
    StringBuilder res = new StringBuilder();
    for (String word: words)
        res.append(reverse(word) + " ");
    return res.toString().trim();
}

public String[] split(String s) {
    ArrayList <String> words = new ArrayList <>();
    StringBuilder word = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == ' ') {
            words.add(word.toString());
            word = new StringBuilder();
        } else
            word.append(s.charAt(i));
    }
    words.add(word.toString());
    return words.toArray(new String[words.size()]);
}

public String reverse(String s) {
    StringBuilder res = new StringBuilder();
    for (int i = 0; i < s.length(); i++)
        res.insert(0,s.charAt(i));
    return res.toString();
}