[프로그래머스] 2020 KAKAO BLIND RECRUITMENT 가사 검색

문제 설명

https://programmers.co.kr/learn/courses/30/lessons/60060?language=java

문제 풀이

• 단순하게 모든 쿼리에 대해 문자열 비교를 한다면 100,000^2 비교가 수행되므로 시간초과가 발생하게 된다.
• 이분 탐색을 통해 비교 횟수를 줄여야한다.
• '?'가 접미사에 오는 경우를 위해 '문자열길이', '앞자리부터 사전순'으로 정렬하는 배열(sortedArray1), '?'가 접두사에 오는 경우를 위해 '문자열길이', '뒷자리부터 사전순'으로 정렬한 배열(sortedArray2) 2개를 만들어 각각의 경우에 대해 이분 탐색을 수행하여 갯수를 카운트한다.
• 맞는 갯수를 모두 카운트하는 방법보다 가장 좌측 인덱스, 가장 우측 인덱스를 찾는 알고리즘으로 짜는 것이 더 좋았을 것이다.

소스 코드 (JAVA)

package com.company;

import java.util.Arrays;
import java.util.Comparator;

public class Main {
    public static String[] arr = {"frodo", "front", "frost", "frozen", "frame", "kakao"};
    public static String[] quries = {"fro??", "????o", "fr???", "fro???", "pro?"};
    public static String[] sortedArr1;  //앞 글자부터 비교
    public static String[] sortedArr2;  //뒷 글자부터 비교
    public static int resultCnt;

    public static void sortArray() {
        sortedArr1 = arr.clone();
        sortedArr2 = arr.clone();
        Arrays.sort(sortedArr1, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (o1.length() > o2.length()) return 1;
                else if (o1.length() < o2.length()) return -1;
                else {
                    for (int i = 0; i < o1.length(); i++) {
                        if (o1.charAt(i) > o2.charAt(i)) return 1;
                        else if (o1.charAt(i) < o2.charAt(i)) return -1;
                        else continue;
                    }
                    return 0;
                }
            }
        });
        Arrays.sort(sortedArr2, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (o1.length() > o2.length()) return 1;
                else if (o1.length() < o2.length()) return -1;
                else {
                    for (int i = o1.length() - 1; i >= 0; i--) {
                        if (o1.charAt(i) > o2.charAt(i)) return 1;
                        else if (o1.charAt(i) < o2.charAt(i)) return -1;
                        else continue;
                    }
                    return 0;
                }
            }
        });
    }

    public static void binarySearch1(int begin, int end, String target) {
        int mid = (begin + end) / 2;
        String temp = sortedArr1[mid];
        if (begin <= end) {
            if (target.length() < sortedArr1[mid].length()) binarySearch1(begin, mid - 1, target);
            else if (target.length() > sortedArr1[mid].length()) binarySearch1(mid+1, end, target);
            else {
                for (int i = 0; i < target.length(); i++) {
                    if (target.charAt(i) == '?') break;
                    if (target.charAt(i) < sortedArr1[mid].charAt(i)) {
                        binarySearch1(begin, mid - 1, target);
                        return;
                    }
                    else if (target.charAt(i) > sortedArr1[mid].charAt(i)) {
                        binarySearch1(mid+1, end, target);
                        return;
                    }
                    else continue;
                }
                // 모두 같을 경우
                resultCnt++;
                binarySearch1(begin, mid - 1, target);
                binarySearch1(mid+1, end, target);
            }
        }
    }

    public static void binarySearch2(int begin, int end, String target) {
        int mid = (begin + end) / 2;
        String temp = sortedArr2[mid];
        if (begin <= end) {
            if (target.length() < sortedArr2[mid].length()) binarySearch2(begin, mid - 1, target);
            else if (target.length() > sortedArr2[mid].length()) binarySearch2(mid+1, end, target);
            else {
                for (int i = target.length()-1; i >= 0; i--) {
                    if (target.charAt(i) == '?') break;
                    if (target.charAt(i) < sortedArr2[mid].charAt(i)) {
                        binarySearch2(begin, mid - 1, target);
                        return;
                    }
                    else if (target.charAt(i) > sortedArr2[mid].charAt(i)) {
                        binarySearch2(mid+1, end, target);
                        return;
                    }
                    else continue;
                }
                // 모두 같을 경우
                resultCnt++;
                binarySearch2(begin, mid - 1, target);
                binarySearch2(mid+1, end, target);
            }
        }
    }

    public static void main(String[] args) {
        int[] result = new int[quries.length];
        sortArray();
        //쿼리에 대해 반복
        for (int i = 0; i < quries.length; i++) {
            resultCnt = 0;
            if (quries[i].charAt(0) != '?') binarySearch1(0, arr.length - 1, quries[i]);
            else binarySearch2(0, arr.length - 1, quries[i]);
            result[i] = resultCnt;
        }

        for (int i = 0; i < result.length; i++)
            System.out.print(result[i] + " ");
        System.out.println();
    }
}