2. 메뉴 리뉴얼
조합 문제
메뉴 리뉴얼 문제는 NM 시리즈변형 문제였다! N개 중에 M개를 선택해서 순열을 만드는 것인데
이 메뉴 리뉴얼 문제에서 변형된 것은 N개가 배열로 여러개 주어진다는 점과 선택하는 M개 또한 숫자가 아니라 문자열로 여러개 주어진 다는 점이다.
N : N개 중에서 선택한다 => orders 문자열 배열에서 각 문자열의 문자들 중에서 선택한다!
M : M개를 선택한다 => course 정수 배열에서 각 숫자에 해당하는 갯수만큼 선택한다!
=>반복문 구조는 course{2,3,4} 의 각 원소마다 orders의 모든 문자열의 조합을 만들어야하기 때문에 course-for { orders-for {..}} 이렇게 된다!
알고리즘 so simple and EZ
course[i]개의 모든 가능한 문자열 조합을 map에 저장한다.
최빈값 갖는 문자열을 우선순위 큐에 저장하고, 이를 다시 문자열 배열에 저장 후 리턴하면 된다!
디테일
역할분담을 철저히!
find 함수⭐️⭐️⭐️⭐️⭐️
문자열 조합을 만들어서 map에 만든 문자열과 빈도수를 저장한다!
동일한 갯수의 문자열을 만들었을 때 최빈값을 m에 저장한다!! ex) ABC : 5, BCE : 7 이면 BCE를 저장.
그리고 리턴되고 나면 for-each문으로 map에 저장된 모든 문자열을 순회하면서 길이가 2이상이고, 최빈값을 갖는 문자열을 우선순위큐에 넣는다!!!
find 재귀함수가 리턴되고 나면 map에 저장된 메뉴 조합인 문자열(key)들을 keySet()으로 하나씩 조회해서 빈도수 최댓값인 m인지 조건 검사해서 해당 문자열이 빈도수 최댓값을 갖는 문자열이라면 우선순위 큐에 저장한다.
=>빈도수 최댓값 찾을 때 왜 find함수에서 바로 map에 안 넣지? 왜 리턴하고 나서 넣나? =>find함수에서는 문자열 순열 생성에서 Map에 넣고, 최댓값 갱신하는 것까지 하고, orders[i]마다 모든 문자열들을 다 연산한 후에 최종적인 Map에서 한번에 일괄적으로 수행한다!
map에는 현재 문자열에서 최빈값 갖는 문자열을 넣는다.
반복문을 다시 살펴보면 N개 중 M개 선택할 때 M에 해당하는 course-for문 안에 orders-for문이 있다. N에 대해 각 문자열의 조합을 만들어야하기 때문이다. 이 orders-for문 i번째 문자열이 N애 해당한다. M개의 문자열 만들 때마다 최빈값 갖는 문자열을 선택하는 것이 목표다. 따라서 orders{2,3,4} 배열의 길이만큼, 해당 원소 개의 문자열 만들 때마다 최빈값 갖는 문자열 선택해서 어딘가에 저장해야하기 때문에 이 때 자료구조를 map으로 생성하여 저장한다.
문자열 배열에 우선순위 큐에 저장된 것들을 다 넣어서 이 문자열 배열을 리턴해주면 된다!
생각한 부분, 내가 접근한 방법
0. 매개변수 orders의 메뉴(알파벳들)을 사전순으로 정렬한다.
ex) ABCFG, AC, CDE, ACDE, BCFG, ACDEH
=> ABCFG, AC, ACDE, ACDEH, BCFG, CDE 이런식으로 정렬하고
각 손님마다 해당 메뉴(알파벳)이 있으면 1을, 없으면 0으로 저장한다.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
단품메뉴 손님번호 | A | B | C | D | E | F | G | H |
1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
2 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
3 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
4 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
5 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
6 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
빈도 수 | 4 | 2 | 6 | 3 | 3 | 2 | 2 | 1 |
빈도수 만족 : 각 index번째 요소끼리 덧셈해서 결과가 course[i]개 이상인 것을 고른다! ex) course[i] = 3이면 빈도수가 3이상인 것들만 해당된다.
동시 만족 조건 : course[i]개 이상인 인덱스끼리 조합해서 서로 &연산했을 때 1이 되는 것을 찾는다 ex) 빈도 수가 3이상인 것은 A, C, D, E가 있다. 이 중에서 동시에 3개가 존재하는 것을 찾아야 하기 때문에 0234 인덱스로 조합을 만들어서 각 인덱스의 값을 & 해서 1이 되는 경우 해당 인덱스의 문자를 더해서 최종 문자열을 만든다.
정답 : 1,2 조건 만족하는 index 번째 문자 더한 것이 정답이 된다!
연산의 목표 : 조합을 이용해 조건을 만족하는 최종 문자열을 만드는 것이다. 위의 방법으로 하면 다소 복잡하기 때문에 풀었던 순열과 조합 문제의 고전적인 재귀함수 풀이 방법으로 한다. (NM 시리즈 참고)
정답 솔루션 재귀 함수로 orders[i]의 모든 메뉴 마다 문자 조합을 만들어서 Map<String, Integer> 로 저장한다. String은 코스 요리 조합(조합한 문자열)이고, Integer는 빈도 수이다.
orders : 각각의 손님들이 주문한 단품 메뉴. ex) {"XYZ", "XWY", "WXA"} course : 코스 요리 갯수 ex) {2,3,4}
course 배열에 저장된 만큼 코스 요리 갯수에 해당하는 문자 조합을 만들어야 한다.
1을 orders의 각 원소마다 반복한다.
2번째로 풀었을 때 ① N! 으로 재귀함수 구현 ② 선택관점으로 2^N으로 재귀함수 구현 => 2가지 방법으로 풀어봤을 때, 당연히 ②이 더 빠를 거라고 생각했는데 대부분의 테스트 케이스에서 의외로 ①이 더 빨랐다.
3번째로 풀었을 때 틀린 이유 실수
정답을 저장하는 배열을 전역변수, 로컬변수 이중으로 있다보니까 비동기화되어
어떤 것은 초기화를 했고, 어떤 것은 그렇지 않았기 때문 NullPointerException이 발생히버렸다. => 변수를 하나로 만들고 초기화함으로써 해결
순열 생성하는 재귀함수에서 정답 찾은 경우 리턴을 안 해버림.
몰라서 틀린 부분
로직을 반복하는 범위, 스코프 문제 : 정답배열에 동일한 문자열들이 존재했다. 정답배열은 우선순위 큐를 그대로 배열로 변환한 것이기 때문에 이 결과는 즉, 우선순위 큐에 동일한 문자열들이 존재한다는 것을 알 수 있었다. 아래와 같은 순서로 데이터들이 저장되는데, 재귀함수에서 Map으로 저장하는 부분은 로직이나 코드에 전혀 틀림이 없었다. Map에서 우선순위 큐에 조건검사를 해서 데이터를 넣는데 이 때 뭐가 잘못된 것인가? 그렇다. 정답배열 <= 우선순위 큐<= Map <= 재귀함수 아래 로직에서 1,2만 for문으로 orders의 모든 원소에 대해 반복하는 것이고, 3번은 1,2가 끝난 후에 course[i]의 Map에 대해 1번만 수행하는 것인데 1,2의 반복문에 들어가서 반복적으로 수행했기 때문에 큐에 동일한 문자열이 여러번 들어간 것이였다. 1번만 수행하는 로직이기 때문에 Map에 동일한 key값이 존재하는지 확인하는 부분도 불필요한 것이고, 이 로직을 반복문 안에 잘못 위치시켜서 발생한 문제였다. => 반복문 밖으로 빼내어 해결✅
Map 활용 능력 : 문자열 순열을 다 만든 경우, Map에 해당 문자열이 존재하는지 확인하고, 있다면 value값을 1 증가시키고, 없다면 새로 <key,value> 쌍을 만들어 1로 만들어야 한다.
Map.getOrDefault(Object key, V defaultValue) Map에서 찾고자하는 문자열 str에 대해 map.put(str, ) put으로 키값 쌍을 넣는 구문으로 구현한다. 이 때 값에 해당하는 파라미터로 Map.getOrDefault를 사용한다. 해당하는 키가 map에 있다면 그에 해당하는 값을 리턴하고, 없다면 Map.getOrDefault의 2번째 파라미터의 값을 리턴한다! 여기에 0을 넘겨주면 해당하는 키가 존재하지 않다면 0을 리턴한다. => put의 2번째 파라미터로 Map.getOrDefault(str,0) +1 로 하여 map.put(str, map.getOrDefault(str,0) +1) 로 함으로써 있으면 해당 value에 1 더하고, 없으면 0을 리턴하여 0에 1 더한 값이 셋팅된다! =>만약에 이미 키값이 존재한다면? put으로 되어있는건 어찌됐든 <key(str),value> 쌍을 map에 넣는 것 아닌가..?그러까 Map에 키값이 있는지부터 먼저 조건검사하고, 있는지 없는지에 따라 따로 구현해주어야하는 것 아닌가? put에 이미 있는 key값을 넣으면 어떻게 되나? <key, 2> 가 있다고 하자. 이후에 <key,4>를 넣으면 어떻게 되나? key는 중복되면 안 되지 않나? =>Map에서 키가 중복되면 기존의 값을 덮어쓴다고 한다! 그렇기 때문에 put으로 이미 존재하는 동일한 key에 대해 value값을 넣어줘도 기존의 값을 덮어쓰기 때문에 기존의 key에 대한 value를 먼저 조회하여 1 더한 값으로 덮어쓰게 된다!
Last updated
