# 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**\
&#x20;     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()){\
   &#x20; String key = it.next();//it는 keySet() 를 순회. keySet은 map의 key(String)으로 이루어진 Set\
   &#x20; List\<Integer> list = map.get(key);\
   &#x20; 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++){\
   &#x20; 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())**{ //다음 것이 있을 때까지만 반복. 없으면 종료!\
   &#x20; **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을 수행해야한다고 생각했다. => 완전히 완벽하게 틀림!\ <br>

   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 코드 :&#x20;

```java
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 에대한 부분을 제거했다.

```java
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);
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://heunnajo.gitbook.io/algorithms-problem-solving-skills/undefined-4/untitled-1.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.