프로래머스 Lv2 순위 검색 문제

• 프로래머스 Lv2 순위 검색 문제
  • 해당 문제의 난이도 상승 원인
    • 각 문자열의 구분자들을 처리하는 방법으로 split 등을 사용 시, 메모리 과부하로 인해 실패
    • 각 입력값에 대한 경우의 수로 나올 수 있는 문자열이 많음
  • 해당 문제를 해결한 방법
    • split과 비슷한 결과를 도출하지만 내부 메모리를 절약할 수 있는 Pattern + Matcher을 사용한 방법으로 해결
    • 경우의 수를 문자열이 아닌 정수를 이용해 생성하도록 함
  • 처음 방식에서 변경한 방식
    • 처음
      • 정규식 + split으로 문제를 해결하려 하였으나 이를 사용 시, 1개의 String이 N개의 크기를 가진 String 배열로 생성되어 메모리 과부하
    • 변경
      • Pattern + Matcher를 사용한 순환 방법으로 메모리 절약을 통해 해결
  • 문제의 핵심
    • 들어온 원시 데이터를 전처리할 시, 이를 어떻게 메모리를 절약하면서 정제를 해야하는지가 핵심
    • 경우의 수 생성 시, 원본 데이터와 반드시 같은 자료형을 사용하지 않아도 해결할 방법이 있는지 알아보는 작업의 필요성

import com.sun.jdi.IntegerType;

import javax.xml.stream.events.StartDocument;
import java.util.*;
import java.util.regex.Pattern;
import java.util.regex.Matcher;
import java.util.regex.MatchResult;
import java.util.regex.PatternSyntaxException;

public class SearchRanking {
    public static void main(String[] args){
        String[] info = {
                "java backend junior pizza 150",
                "python frontend senior chicken 210",
                "python frontend senior chicken 150",
                "cpp backend senior pizza 260",
                "java backend junior chicken 80",
                "python backend senior chicken 50"
        };

        String[] query = {
                "java and backend and junior and pizza 100",
                "python and frontend and senior and chicken 200",
                "cpp and - and senior and pizza 250",
                "- and backend and senior and - 150",
                "- and - and - and chicken 100",
                "- and - and - and - 150"
        };

        solution(info, query);
    }

    public static int[] solution(String[] info, String[] query){
        Map<String, List<Integer>> map = new HashMap<>();
        Map<String, Integer> table = new HashMap<>();

        table.put("-", -1);
        table.put("java", 0);
        table.put("cpp", 1);
        table.put("python", 2);
        table.put("backend", 3);
        table.put("frontend", 4);
        table.put("senior", 5);
        table.put("junior", 6);
        table.put("pizza", 7);
        table.put("chicken", 8);

        StringBuilder sb = new StringBuilder();

        // 내가 생각한 [1,1,1,1]은 결국 비트마스크와 다를 것이 없다
        Pattern pattern = Pattern.compile(" ");
        Matcher matcher = pattern.matcher("");
        int[] datas = new int[4];
        for(String inf : info){
            matcher.reset(inf);
            int spaceLastEnd = 0;
            int dataIdx = 0;
            while(matcher.find()){
                datas[dataIdx++] = table.get(inf.substring(spaceLastEnd, matcher.start()));
                spaceLastEnd = matcher.end();
            }

            int score = Integer.parseInt(inf.substring(spaceLastEnd, inf.length()));

            for(int i = 0; i < 16; i++){ // i는 경우의 수를 나타내고
                for(int bit = 0; bit < 4; bit++){ // bit는 0이 아니면 해당 값을 넣고 0이면 -를 넣음
                    if((i & (1 << bit)) != 0){
                        sb.append(datas[bit]);
                    }
                    else{
                        sb.append(-1);
                    }
                }

                if(map.get(sb.toString()) == null) map.put(sb.toString(), new ArrayList<>());
                map.get(sb.toString()).add(score);

                sb.setLength(0);
            }
        }

        for(List<Integer> scores : map.values()){
            Collections.sort(scores);
        }

        pattern = Pattern.compile(" and ");
        matcher = pattern.matcher("");

        List<Integer> list = new ArrayList<>();
        for(String s : query){
            matcher.reset(s);
            int lastEnd = 0;

            while(matcher.find()){
                sb.append(table.get(s.substring(lastEnd, matcher.start())));
                lastEnd = matcher.end();
            }

            int lastSpace = s.lastIndexOf(" ");
            sb.append(table.get(s.substring(lastEnd, lastSpace)));
            int target = Integer.parseInt(s.substring(lastSpace + 1));

            List<Integer> scoreList = map.get(sb.toString());

            if(scoreList == null){
                list.add(0);
                sb.setLength(0);
                continue;
            }

            int left = 0;
            int right = scoreList.size();

            while(left < right){
                int mid = (left + right) / 2;

                if(scoreList.get(mid) >= target){
                    right = mid;
                }
                else{
                    left = mid + 1;
                }
            }

            list.add(scoreList.size() - left);

            sb.setLength(0);
        }

        return list.stream().mapToInt(Integer::intValue).toArray();
    }

}