Pccp 준비하기 - 5 이진탐색과 문자열 정렬

정렬관련 문제를 이틀간 풀어보면서 단순 정렬하는것보다 나은 방식이 뭐가 있을지 고민하는 법을 배우게 되었다

자바에서 배열과 컬렉션 정렬과 복사하기

int [] array = {1,3,5,7,9};
Arrays.sort(array);

List<Integer> collection = new ArrayList<>(List.of(5,8,7,9));
Collections.sort(collection);

복사의 경우 copyOfRange(배열, 시작위치, 끝위치(포함안됨)) 이 메서드를 사용하면 된다

int [] c = Arrays.copyOfRange(array, from, to);
Arrays.sort(c);

객체끼리 비교하는 인터페이스 - Comparator

객체끼리 값을 비교하는데 있어 자바에서는 유용한 인터페이스인 Comparator가 있다!
Comparator 인터페이스 내부 compare함수를 정의하면 된다!

인터페이스 원형

public interface Comparator<T> {
	int compare(T o1, T o2);
}

활용

Arrays.sort(nums, new Comparator<String>() {
	public int compare(String o1, String o2) {
    	return (o2 + o1).compareTo(o1 + o2);
    }
}

이진탐색

내부 전부를 탐색하는 것이 아닌 정렬된 배열이나 객체를 절반씩 잘라가면서 도는 방식이다
이러면 logN까지 반복이 줄게 되므로 효율적으로 코드를 작성할 수 있게 된다

정렬된 상태일때 사용가능한 이진 탐색 메서드

int arrayIdx = Arrays.binarySearch(array, 8);
int listIndex = Collections.binarySearch(list, 8);

이진탐색 프로그래머스 문제 - 순위 검색

순위 검색 링크

이 문제는 전부 탐색을 하게 되면 50억번을 반복하므로 이진탐색을 필수로 해야한다!
그렇기에 각 나올 수 있는 문자열을 전부 조사해서 각 리스트에 value를 넣어준다

import java.util.*;

class Solution {
	static HashMap<String, List<Integer>> map;
    
    public int[] solution(String[] info, String[] query) {
    	int [] answer = new int[query.length];
        map = new HashMap<>();
        
        // map에 모든 info의 string넣기
        for (int i = 0; i < info.length; i++) {
        	String [] infoArray = info[i].split(" ")
            makeSentence(infoArray, "", 0);
         }
        
        // map의 각 부분들 리스트 정렬하기
        for (String s : map.keySet()) {
        	Collections.sort(map.get(s));
        }
        
        // 이제 query돌면서 각 스코어보다 높은애 몇개나 있는지 찾고 answer에 넣기
        for (int i = 0; i<query.length; i++) {
        	query[i] = query[i].replaceAll(" and ", "");
            String [] q = query[i].split(" ");
            answer[i] = map.containsKey(q[0]) ? binarySearch(q[0], Integer.parseInt(q[1])) : 0;
        }
        
        return answer;
    }
    
    private static int binarySearch(String key, int score) {
    	List <Integer> list = map.get(key);
        int start = 0;
        int end = list.size() -1;
        while(start <= end) {
        	int mid = (start + end) / 2;
            if (list.get(mid) >= score) {
            	end = mid - 1;
            } else {
            	start = mid + 1;
            }
        }
        return list.size() - start;
    }
    
    private static void makeSentence(String [] p, String str, int count) {
    	if (count == p.length - 1) {
        	if (!map.containsKey(str) {
            	List<Integer> list = new ArrayList<>();
                map.put(str, list);
            }
            map.get(str).add(Integer.parseInt(p[4]));
        }
        makeSentence(p, str + "-", count+1);
        makeSentence(p, str + p[count], count+1);
    }
}