3. 순위 검색

이 문제 또한 메뉴 리뉴얼과 비슷하게 순열 조합 문제다. 또한, 정확성과 시간 효율성을 고려하여 이분 탐색으로 구현하는 것이 관건이다!

어려웠던 점

  1. 이분탐색으로 리스트에서 최솟값 인덱스 찾는 것. 같은 점수가 여러개 있을 수 있고, 어떤 경우에는 리스트의 모든 점수가 같을 수 있기 때문에 이에 대한 모든 경우에 대해 정확하게 최솟값 인덱스를 찾아서 만족하는 총 갯수를 리턴할 수 있어야 한다.

  2. Map 사용

  3. 백준에서 NM2 선택관점 + 다음 순열 문제를 조합한 문제였다. 백준에서 하나의 문제였던 알고리즘을 순위 검색 문제에서는 컬렉션으로 주어지는 느낌. 큰 문제 안에 작은 문제들 큰 문제 : info 배열 크기만큼 반 작은 문제 : info배열에서 각 원소에 대해 순열을 만들어야함 =>각 원소에 대해 NM2(선택) + 다음 순열

  4. 공백과 데이터가 섞인 문자열을 split을 사용해서 공백 제거하고, 유의미한 데이터들만을 String에 += 로 생성하는 것.

  5. 매일 쓰지만 이렇게 활용될 줄은 몰랐던, .split(" ") 의 반환값은 String[ ]이고, 각각은 String이기 때문에 정수라면 Integer.parseInt()로 형변환해주어야한다는 점.

핵심 자료구조 및 알고리즘

  1. Map<String, List<Integer>> : 모든 가능한 경우의 수 String과 해당하는 점수를 list 저장 => {String, list} 쌍으로 저장한다. key : 모든 가능한 경우의 수 String, value : 모든 경우의 수에 해당하는 점수를 list에 저장.

  2. 이분 탐색 : 순차적으로 탐색하면 시간초과 발생하기 때문에 이분 탐색한다.

매개변수

  1. String[ ] info : 지원서에 입력한 4가지의 정보, 코테 점수 // 총 5개의 데이터

  2. String[ ] query : 문의 조건

자료구조⭐️⭐️⭐️⭐️⭐️

Map<String, List<Integer>> : <문의 조건, 조건에 부합하는 사람들의 점수 리스트> ex) key : 문의 조건 String ex) javabackendjuniorpizza150 value : 조건 부합 점수들 ex) [50,80,150,150,210,260]

로직 흐름 정리

  1. info 배열의 각 문자열 원소로 만들 수 있는 모든 경우의 수를 다 구한다. => Map의 key

  2. 각각의 경우의 수에 부합하는 사람의 점수를 List에 저장한다. => Map의 value

  3. 정답 : String[ ] query 배열의 각 문의조건(key)로 점수 List(value)를 찾는다. key : javabackendjuniorpizza // "and"와 마지막 데이터(점수)를 제외한 문의 조건 value : [50,80,150,150,210,260] // x=150이라면 리스트에서 150인 최솟값 인덱스를 찾는다. => 리스트 크기 - 최솟값 인덱스 = 정답이 된다!

메인 메서드 Solution 구조 makeMap(info);//내부에서 dfs 재귀함수로 모든 가능한 문자열 순열 생성 makeAnswer(query);//내부에서 counting(String Condition, int scoreX)로 조회하는 문의 조건에 해당한는 사람이 몇명인지 answer 배열에 저장.

2번째 풀었을 때 틀린 이유

  1. 리스트를 오름차순 정렬해줘야한다고 생각했는데 구현하는 걸 깜빡했다. makeMap(info) 메서드 내에서 dfs 재귀함수 호출 후 Map 생성한 후에 Map의 value인 List를 오름차순 정렬해야한다. => Collections.sort()로 편하게 오름차순 정렬할 수 있지만, List를 순회하면서 값을 변경하기 위해서는 Iterator를 사용해야 한다! (Iterato 문법⭐️) Map의 모든 key를 순회하면서 각 key의 value List를 정렬해야 한다! Iterator<String> it = map.keySet().itereator(); while(it.hasNext()){ String key = it.next();//it는 keySet() 를 순회. keySet은 map의 key(String)으로 이루어진 Set List<Integer> list = map.get(key); Collections.sort(list); }

  2. 메서드 이름 틀림(minor한 이슈. 자바 API 문서 참고하면 되지만 알아두면 좋다!) map에 key가 있는지 확인 : map.containsKey(key) map에 (key,value) 추가 : map.put(key,value) 배열의 길이 확인 : .length ❌.length()❌

  3. makeAnswer : i번째 info split처리만 해서 dfs 3번째 매개변수로 넘겨주면 됨. //1.i번째 문자열마다 재귀함수 dfs호출. for(int i=0;i<info.length;i++){ dfs(0,"",info[i].split(" ");//Map 완성 } //2.Map의 value인 List 정렬

  4. .split(" ")의 결과는 String [ ] 이기 때문에 점수에 해당하는 것은 Integer.parseInt(info[4])처리해줘야한다!!!

  5. makeAnswer(query) : 내부에서 query배열 원소를 split과 적절 처리하여 문의조건, 점수x로 필터링하고, counting(String Condition, int scoreX)로 조회하는 문의 조건에 해당한는 사람이 몇명인지 리턴.

정확성, 효율성 테스트 틀린 이유(feat.이분탐색) 최솟값 인덱스 찾는 것이 어려웠다. : counting메서드에서 리스트에서 점수가 X이상인 갯수를 카운팅할 때, 리스트에서 X인 요소의 최솟값 인덱스를 찾아야한다! 동일한 점수가 있을 수 있기 때문이다!

극단적인 예를 들어, list = [150,150,150,150,150,150] 인 경우 기존의 코드인 list.get(mid) == score일 때 반복문을 종료하는 코드에서 list.get(mid) == score을 만족하기 때문에 인덱스는 2가 되고, 4가 출력된다. 우리가 원하는 최솟값 인덱스는 0인데 말이다!

다시 반복문의 조건을 생각해보자. 우리가 원하는 최솟값 인덱스를 s에 저장한다. while(s <= e) {..} 인동안 반복한다. 즉, s와 e는 결국 같아지기 마련이다. 이 때, s==e==mid가 된다. 우리가 찾는 것은 최솟값 인덱스이기 때문에, s== e==mid일 때, 그 인덱스는 x보다 인덱스가 1작은 인덱스를 찾아야 한다. 바로 다음 인덱스가 x가 시작하는 최솟값 인덱스가 되기 때문!⭐⭐️⭐️⭐️⭐️ s==e==mid일 때까지 반복하고, s==e==mid는 x보다 1 작은 인덱스로써, if(list.get(mid)<score)을 만족하여 s=mid+1 이 되고, s>e가 되어 반복문 탈출하여 s에 최솟값 인덱스가 저장되는 것이다❌ => 일반화할 수 없음. 다시 시뮬레이션해보면 [150,150,150,150,150,150], [50,80,150,150,150,210,260] 일 때 둘 다 list.get(mid) == score 일 때 e=mid-1이 되어 e<s가 되면서 s는 정수 X가 처음 등장하는 인덱스를 가리키게 된다.

Iterator 사용 map의 모든 key의 value 리스트를 정렬해야한다! (x이상인 점수 갯수를 카운팅하기 위해) =>리스트를 순회하면서 정렬하여 값을 변경하는 것이기 때문에 Iterator를 사용해야한다!

  1. 모든 key를 가져온다 : map.keySet()

  2. 반복할 반복자 정의 - 반복할 대상(컬렉션) : map.keySet() => .iterator() 대상 - 반복할 변수 : keySet()에서 각각의 key(String) => Iterator의 제너릭 => Iterator<String> it = map.keySet().iterator();⭐️⭐️⭐️⭐️⭐️

  3. iterator 반복문 생성 while(it.hasNext()){ //다음 것이 있을 때까지만 반복. 없으면 종료! String key = it.next();// iterator.next()로 대상 컬렉션(keySet)에서 하나씩(key) 가져온다!

  4. key로 value 리스트 조회하여 정렬 : Collections.sort(list)

3번째 풀고 정답과 다른 부분 & 틀린 부분 중구난방으로 여기저기서 틀린 것 투성이 느낌. => 정답과 구현되있는 구조는 좀 다르지만, 필요한 로직 구현은 갖추었다. 그래도 재귀함수와 Iterator를 사용한 부분은 완벽하게 구사하였다.

  1. 문자열 순열을 만들어 Map<String,List<Integer>> 형식으로 저장하는 것까지는 생각했다. String 하나에 대해서 존재한다고 생각해서 query[i]마다 Map이 필요하다고 생각했다. 하지만 입력부분을 다시 살펴보면, info배열 전체를 순회하면서 info[i]로 모든 가능한 문자열 순열을 만들고, 이것은 마치 사전처럼 Map에 저장하여 query[i]마다 조건을 이 Map에 찾아서 정답을 도출하는 것이기 때문에 Map은 전역 변수로 하나만 있으면 된다!

  2. 구현된 메서드 별 역할 ① (기존)int[ ] Solution : query배열을 순회하면서 문자열을 파싱하여 조건과 점수로 분리하여 추출! ② void mainLogic(String[ ] info) : 처음에는 문제에서 주어지는 info배열과 query배열 모두 필요하다고 생각하여 2개의 파라미터로 구성했지만, 이 메서드의 본질, 목적은 info배열 전체를 순회하여 info[i]마다 문자열 순열을 만드는 것이기 때문에 파라미터로 query도, query를 순회하는 반복문도 불필요하다는 것을 깨달았다! ③ void sorting() : 1번에서 Map을 전역변수로 설정함으로써 매개변수를 삭제하여 코드가 간결해졌다. ④ int getAnswer(String cmd,int score) : 이 또한 마찬가지로, Map을 전역변수로 설정하는 것을 이해하면 전역변수인 Map의 valuu인 리스트를 쉽게 조회하여 가져올 수 있다. => 리스트를 이분 탐색하는 부분에서 탐색을 반복하는 while문 조건은 while(s<=e) 이고, 내부에서 s 또는 e는 반복이 되는 동안 계속해서 갱신되기 때문에 이에 따라 mid 또한 반복적으로 갱신해주어야한다! while문 밖에 초기 mid만 설정해주고 더 갱신해주지 않아서 틀림. while문을 반복하는 조건이 s<=e이기 때문에 s>e가 되면 반복을 종료한다. s의 값이 바뀜으로써 whil문을 탈출한다고 생각했고, s=e=mid=score가 되는 시점이 발생한다면 그 때, s값이 변해야 하므로 mid==score일 때 s = mid+1을 수행해야한다고 생각했다. => 완전히 완벽하게 틀림!

    ex1) [150,150,150,150,150,150] ex2) [50,80,150,150,150,210,260]

    ex1, ex2 모두 list.get(mid) == score일 때 e=mid-1을 수행하여 결과적으로 s는 정수 X가 등장하는 첫 인덱스를 가리킨다.

    시뮬레이션해보면 s=e=mid=score인 시점에서 e=mid+1 가 되어 e<s가 되면서 while문을 종료하는 것이 올바른 동작이다. 이 때 s는 정확히 찾고자하는 점수가 처음 시작되는 인덱스를 가리키고 있다.

기존의 mainLogic, sorting 코드 : 

static void mainLogic(String[] info,int[] query){
        for(int i=0;i<query.length;i++){
            //map = new HashMap<>();
            for(int j=0;j<info.length;j++){
                //재귀함수 실행:문자열 순열 생성
                //1.문자열 파싱
                String[] infoArr = info[j].split(" ");
                go(0,"",infoArr);
                
            }
            sorting();//sorting(map);//전역변수라서 굳이 매개변수로 전달하지 않아도 됨!
        }
    }
    static void sorting(HashMap<String,List<Integer> map){
        //map의 모든 key에 대한 value를 정렬한다!
        Iterator<String> it = map.keySet().iterator();//keySet을 반복한다.String의 집합.
        while(it.hasNext()){
            String s = it.next();
            List<Integer> list = map.get(s);
            Collections.sort(list);
        }
    }

리팩토링 후 간결해진 코드 : Map을 전역변수로 하나만 만듦으로써 sorting의 매개변수는 사라지고, mainLogic도 불필요한 query 에대한 부분을 제거했다.

static void mainLogic(String[] info){
    for(int j=0;j<info.length;j++){
        //재귀함수 실행:문자열 순열 생성
        //1.문자열 파싱
        String[] infoArr = info[j].split(" ");
        go(0,"",infoArr);   
    }
    sorting();
}
static void sorting(){
    //map의 모든 key에 대한 value를 정렬한다!
    Iterator<String> it = map.keySet().iterator();//keySet을 반복한다.String의 집합.
    while(it.hasNext()){
        String s = it.next();
        List<Integer> list = map.get(s);
        Collections.sort(list);
    }
}

Previous2. 메뉴 리뉴얼Next다익스트라 알고리즘

Last updated