탐색 영역과 비교군을 명확히 하기
단계를 나누고, 적절한 도구를 선택하기
타입과 조건에서 단서 찾기
이 글의 목적은 암기하는 게 아니라 *사고 과정 자체를 학습하기이다.
지난 글에 이어 해시를 알아본다. 이번엔 처음 풀어본 문제로 사고 과정과 실패 원인, 동작 원리를 분석했다. 제한 시간 30분 동안 프로그래머스의 정답률 34%의 레벨 2 문제를 풀었다. 노트에 추상 구현에만 작성하다가 시간이 초과되었고, 결국 실제 코드 작성 조차 못한 채 실패했다. 하지만 30분 동안의 사고 과정을 전부 작성했기에 복기할 수 있다.
문제
지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때, 각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
함수 인자:
info :
["java backend junior pizza 150",...,"python backend senior chicken 50"]
query:
["java and backend and junior and pizza 100",...,"- and - and - and - 150"]반환값:
// 조건 query[i]에 해당하는 info[i~n]의 숫자를 0~query.length-1 순서대로 배열에 저장
[1,1,1,1,2,4] 제한 사항:
info 배열의 크기는 1 이상 50,000 이하입니다.
info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
query 배열의 크기는 1 이상 100,000 이하입니다.
조건은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.언어/직군/경력/소울푸드는 (....), - 중 하나입니다.
'-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
실패한 추론 과정
문제 분석
문제를 분석했다. 가장 눈이 가던 부분은,
info,queryO(n^2)으로 풀 수 없다.query로info를 탐색해야 한다.모두 문자열로 되어있지만, 객체처럼 기능한다.
info,query는 동일한 필드를 갖지만 서로 형태가 다르다 - "and"와 "-"가 query에 있다.info는 모든 필드가 들어있고,query는 숫자를 제외한 모든 필드가 nullable이다.코딩테스트 점수만 숫자 타입이다.
info,query에 모두 들어있다.코딩테스트 점수만 완전 일치가 아닌 X 이상 이라는 조건이다.
query의 조건 조합 자체가 '키key'가 되어야 한다.이 키로 O(1) 탐색을 해야한다.
query[i]조건에 해당하는info[i]가 여러 개이다.
추론 과정
구현에 앞서 손으로 그래프를 그리며 구현 과정을 작성했다.
graph TD;
A["A.답을 모으는 쿼리는 query O(n) 순회. 순회 과정에서 해시를 O(1)로 탐색"] --> B;
B["B.첫번째 조건은 적절한 키로 해당하는 info[i~n] 요소들을 얻음"] --> C;
C["C.두번째 조건을 점수로 하고, 현재 값 점수 이상을 통과하는 요소들만 필터링"] --> D;
D["D.문자열 조건은 query[i]가 info[i]의 부분집합"] --> E;
E["E.Set 메서드의 부분집합으로 현재 쿼리에 해당하는 요소만 거르고, 점수를 판별"] --> F;
F["Fin: 저장된 갯수 반환"]
실제 구현을 위한 추론 과정은 더 길었다:
graph TD;
Q1["Q1. 탐색 대상은?"] --> A1["A1. info이다"];
A1 --> Q2["Q2. 탐색 방식은?"];
Q2 --> A2["A2. query를 O(n)으로 순회하면서, info 해시에서 O(1)로 탐색한다"];
A2 --> Q3["Q3. 어떤 객체를 사용하는가?"];
Q3 --> A3["A3. query[i]의 문자열이 '키'로 기능해야 하니 'Map' 또는 'Object'를 사용한다"];
A3 --> Q4["Q4. 해시에서 조건을 어떻게 만드는가?"];
Q4 --> A4["A4. query[i]의 조건-조합이 탐색 시 '키'가 되어야 한다"];
A4 --> Q5["Q5. 구체적으로?"];
Q5 --> A5["A5. 조건 1: query[i]에서 '-', 'and'를 제외한 문자열을 info[i]가 포함해야 한다"];
A5 --> A6["A6. 조건 2: query[i]의 스코어 이상이어야 한다"];
A6 --> Q6["Q6. 어떻게 찾는가?"];
Q6 --> A7["A7. 해시에 등록된 여러 지원자들 info[i~N]을 탐색하여 복수의 결과를 가져와야 한다"];
A7 --> Q7["Q7. 해시는 '키-값' 쌍이므로 하나의 키로 여러 값을 가져올 수 없는가?"];
Q7 --> A8["A8. 값에 배열을 사용한다"];
A8 --> Q8["Q8. 그럼 키는 무엇이 되는가?"];
Q8 --> A9["A9. query[i]의 스코어를 키로 사용한다"];
A9 --> Q9["Q9. 그럼 값은?"];
Q9 --> A10["A10. info[i]가 query[i]의 점수 이상일 때, 해시 키보다 크면 값 배열에 push한다"];
A10 --> Q10["Q10. 어떤 자료구조를 사용하는가?"];
Q10 --> A11["A11. 숫자가 키가 되어야 하므로 Map을 사용한다"];
A11 --> Q11["Q11. 그럼 'Map'의 키는 query이고, 값은 info인가?"];
Q11 --> A12["A12. 맞다. 점수 필터링을 해시 키로 한다"];
A12 --> Q12["Q12. 'Map' 값인 배열에는 어떤 데이터가 들어가야 하는가?"];
Q12 --> A13["A13. query[i]의 문자열은 info[i]의 부분집합이므로 'Set'을 활용하면 좋다"];
A13 --> Q13["Q13. 그럼 query[i]의 문자 부분도 'Set'으로 처리하는가?"];
Q13 --> A14["A14. 맞다. 문자 필터링은 'Set'으로 한다"];
A14 --> Q14["Q14. 점수로 탐색하는 것 자체는 O(1)이지만, 'Map' 값인 배열 요소 비교는 O(n) 아닌가?"]
Q14 --> A15["A15. ...맞다. 그런데 다른 방법이 떠오르지 않는다"]
이 과정에서 폐기된 접근법들은,
info, query를 일반 객체로 만들고 비교
info[i], query[i]를 객체를 만들고 현재 조건 query[i]의 유효한 필드를 Object.entries, values로 탐색
query에서 O(n)으로 탐색이 끝나야 하기 때문에, 배열과 배열 요소 비교는 반복이 추가된다. 폐기query와 info를 문자 부분만 따서 비교
배열과 배열 비교 O(n^2) 방법이므로 폐기.Map에
info[i]문자열을 필드로, 점수를 숫자 배열로
이 경우query[i]의 문자열이info[i]의 부분이어도 찾아내야 하기 때문에 탐색이 안된다.
한계와 오류들
사고 과정 오류: Map(해시) 키-값의 설계 오류
집중해야 할 문제 : 2개의 조건과 배열, 2번의 탐색
핵심 문제: 탐색 최적화 - 어떻게 탐색을 두 번 최적화할 것인가?
사고 과정을 노트로 옮기고 질답을 작성하니 생각의 오류가 분명히 보인다. 특히 핵심 문제를 논리 전개 이전에 의식하지 못한 것이 연속된 실수로 이어졌다.
꼬이기 시작한 지점은 A9부터다. 키를 query[i]의 점수로 사용하는 것. 여기서 초기 추론과 완전히 반대의 선택을 내리기 시작했다.
'점수'만 숫자 타입이므로, 어쩐지 중요한 역할을 할 거라 생각했다.
해시를 만들어야 하는데, 키로 필터링해서 여러 요소를 가져와야한다.
'점수 필터링'이 가장 중요하니 중간 연결고리로 쓰고, 값에는
info[i]의 문자부분만 갖는 Set을 배열로 저장한다.Set에는 부분집합을 검증하는 메서드 isSupersetOf, isSubsetOf가 있다.
쿼리 키(문자열 부분)가 부분집합임을 O(1)로 확인할 수 있을 것 같다.
이후 O(n) 순회에서
query[i]의 점수만으로 O(1) 접근하고, 문자열 부분을 "-", "and" 제거한 단어 Set으로 만들고 부분집합 여부로 갯수를 확인.하지만 Set과 Set 배열의 비교이므로, 여전히 최악의 경우 O(n^2)가 됨
A9의 잘못된 가정에서 시작하니, 배열에 Set을 넣어 O(n) 탐색이 해결하려는 실수를 했다. "2. 첫번째 조건은 적절한 키로 해당하는 info[i~n] 요소들을 얻음"이라고 초기 추론에서 분명 인지했는데, Set이면 해결될 거라 믿고, 잘못된 방법을 고치려는 데 시간을 너무 썼다.
어떻게 키-값을 탐색에 유리하게 만드는가?
처음엔 단순히 두 객체 배열에서 탐색 영역에 조건 해당하는 갯수 새기의 문제라고 여겼다. 하지만 이 문제에서 조건도 여러 개고, 탐색 대상에 해당하는 요소도 여러 개다. 즉 O(1)으로 배열을 먼저 얻고, 그 값들이 query[i]로 필터링하는 과정을 다시 최적화 해야한다. 두 단계의 최적화가 필요함을 제대로 인지하지 못했다.
추론 과정과 뒤집어진 결정을 내린 원인은 시간 압박이다. 어떤 구조의 해시 키-값이 맞지?라고 지나치게 고민하다가 시간 압박에 못이겨 내린 최선의 선택이 오류였던 것이다.
여기서 배운 점은 막혔을 때 질문을 하는 것이다. 테이블을 돌려 지금 막힌 지점에서 유효한 질문을 던지면, 한번에 답에 이르지 않지만, 적어도 한 걸음은 가까워진다. 연쇄된 유효한 질문이 맞는 답으로 데려다 준다. 매번 반복되는 사고 막힘에 대처하는 구체적인 방법은 1.단서를 찾고, 2.거기서로부터 작은 질문과 작은 답을 연속하는 거다.
정답의 추론 과정
결국 30분 동안 생각만 하다가 제한 시간이 모두 지났다. 여기서 더 고민해도 변하지 않는다. 바로 GPT에게 물어보고, 코드를 손으로 작성하며 논리 구조를 파악한다. 그러곤 다시 추론 과정을 복기하여 무엇이 잘못된 생각이었는 지 짚어본다.
문제에서 단서 찾기
1. 자료 구조가 주는 힌트
info: 탐색 대상
직군, 경력 ..., 점수(숫자) 모두 not nullquery: 탐색 조건, query[i]가 개별 조건의 키
직군, 경력...나머지 모두 nullable | 숫자 not null
숫자가 not null인 점을 캐치한 건 좋았다. 여기서 조건은 query[i][점수] 에 해당하는 숫자 이상을 걸러내야 한다. 나머지 모든 문자열은 (부분) 일치가 조건이고, 숫자는 이상이 조건이다. 탐색이 두번 필요하단 것을 자료 구조와 문제 조건이 이미 명시적으로 알려주고 있다.
2. 집중 할 문제
어떻게 탐색을 최적화 하는가? > 어떻게 두 번의 탐색을 최적화하는가?
추론 과정을 돌이켜 보니 탐색 최적화 = "O(n)을 O(1)로 만든다"만 집중했다. 1번의 탐색 O(1)으로 여러 대상 가져오기는 Map의 값이 배열이 되지 않는 이상 불가능하다. 여기까진 맞게 접근했다. 그 이후 키와 값에 각각 어떤 것을 넣을까 고민했다. 여기서 필터링을 키로 직접 구현할 수 있는 형태-에서 질문이 멈췄다. 이 고민의 '목적'을 떠올리면 더 쉽게 다음 질문으로 이어질 수 있다.
Before:
해시 사용해서 O(n) -> O(1) 어떻게 탐색하지?
(탐색이 2번 필요하다는 가정을 인지하지 않았다.)
After:
목적
O(n)에서 O(1)으로 배열을 가져온다. - 첫번째 탐색 최적화
이 배열을 최적화된 방법으로 다시 탐색한다. - 두 번째 탐색 최적화
조건이 2개이고, 찾아야할 대상 info[i~n]도 여러 개니까 탐색을 2번 한다. 2번째 탐색이 필요한 걸 인지하고, Map의 값에 어떤 타입의 배열이 되어야 탐색에 유리할 지, 의미있는 질문을 할 수 있다. Set을 만드는 부분집합이 O(n^2)이 될 걸 알면서도, 키 필터링에 숫자를 쓰는 것 말고 다른 방법이 안 떠올랐다. 그러는 대신에 '필터링 하는 키'보다, 두 번째 배열을 효과적으로 탐색한다-에 집중하면, 더 쉽게 추론했을 것이다.
고민하다가 key에 query[i].점수인 숫자를 넣었다. '필터링 하는 키'를 일단은 찾았으니까. query[i]의 문자열을 조각내어 Map에 추가하는 방법은 도무지 떠오르지 않았다. info[i] 문자의 부분집합인 query[i]의 문자를 어떻게 키로 구현할 방법을 고민하지 않았다. 어렵게 느껴져서 자동적으로 회피했던 것 같다. 문제 조건에 분명 어긋나지만 쉬워보이는 길이 있다면, 이젠 고민도 없이 내려놓겠다.
3. 타입이 힌트
O(1)으로 해시에서 배열을 가져온다. query[i]는 숫자와 문자열로 이루어진다.query[i]가 갖는 조건은
info[i]의 문자열 일부 or 전체가query[i]와 일치info[i]의 숫자(점수)가query[i]의 숫자 이상
정답에 가까운 자료구조를 한번에 얻을 고민을 하기 전에 이렇게 생각해보자.
해시에서 가져온 배열 안에 숫자와 문자 중 어떤 게 탐색에 쉬울까?
이 때 문자를 가져오는 조건은 부분 일치이고, 숫자는 x 이상이다.
이렇게 고민하니 당연히 숫자란 답이 나온다. 문자 탐색 조건이 생각보다 간단하지 않기 때문이다. .includes는 기본적으로 O(n)이라 복잡도가 높다. 거기에 문제에서 문자열 조건은 더 복잡하다. query[i]가 갖는 4개의 필드 중 하나라도 일치하는 info[i]를 찾아야 한다.
키를 점수로 하여 X 이상을 필터링하고, 문자는 Set과 부분집합으로 필터링한다는 막연한 해결법은 잘못된 접근이었다. 방향이 중요하다. 타입과 2개의 조건이 꽤 분명하게 단서를 주고 있다.
원리와 추론 과정
오류를 인지하고 필요한 단서들을 찾았으니, 새로운 방법으로 다시 추론 해본다.
두 배열에서 한 요소로 여러 요소를 가져와야 한다.
가져올 때 조건은 2개다. 문자의 부분 일치와 숫자의 특정 값 이상.
탐색 조건은
query이다.query에서 O(n) 순회를 한다.조건이 2개이니 탐색 과정을 두 단계로 나눠서 진행한다.
1단계 :
query를 O(n)으로 순회하면서 여러 요소를 가져와야 하니 O(1), 키-값 구조가 적절하다. 이 때 가져올 값이 여러 개이니 값은 배열이 되어야한다.2단계 : 가져온 여러 요소를 2번째 조건에 맞춰 탐색한다. O(n)이 아닌 최적화 탐색을 찾는다.
어떻게 1단계를 가져올까?
더 구체적으로, 어떻게 키가 info를 탐색할 수 있게 해시를 만들까?
답을 얻기 위해 초점을 바꿔 단서를 찾는다.
해시에서 키로 값을 가져올 때, 두가지 조건 중 어떤 것을 적용하는 게 나을까?
각 조건을 키로 사용할 때 케이스를 비교한다.
숫자(점수)를 키로 사용: 값이 문자 배열이 된다. 문자 비교는
query[i]가 부분집합이 되어야 한다. 값 배열을 모두 순회하는 방법 밖에 없다.문자를 키로 사용: 배열에서 쿼리 점수 이상만 탐색하면 되니 문자보다 쉽다.
{ [key: string // 선택된 쿼리 문자] : number[] // 지원자들의 점수}키와 값의 타입을 결정했다. 2번째 탐색에서 숫자가 유리하기 때문이다.문자열 키의 조건은
info[i]문자 일부가query[i]문자를 포함할 때이다.query[i]의 문자만으로 키를 찾을 수 있도록hash(x)의 적절한 방식을 고려한다.이 때
hash(query[i])를 사용해 바로 값을 얻을 수 있도록 해시를 설계한다.바로 떠오르지 않는다. 전체 과정을 추론하는 단계이니,
hash(query[i])키를 사용해 바로 값인 숫자(점수) 배열을 가져왔다고 가정한다.해시로부터 점수 배열을 가져왔다. 어떻게 2단계 탐색을 할까?
점수 배열에는 x 이상만 정렬하면 된다. 이 때 O(n)이 되지 않게 filter()같은 메서드는 사용하지 않는다.
특정 숫자 이상의 범위만 알면 된다. 두 개의 포인터를 움직이는 탐색으로 O(n)을 피할 수 있다.
그러기 위해 점수 배열이 미리 sort가 이루어지면 더 편하겠다.
이 탐색이 끝나면, 해시에서 가져온 배열에서 x 이상인 요소 갯수를 알 수 있다. 배열의 갯수는 곧 길이이므로 right - left + 1로 파악 가능하다.
query[i]사이클을 마지막에는 21에서 얻은 길이를 반환할 배열에 push한다.모든 순회가 끝나면 저장된 답변을 반환한다.
적절한 해시 구조 찾기
질문 : 16. 어떻게 문자 키hash(query[i])로 바로 값을 얻을 수 있는 해시를 만들까?
"frontend" -> "frontend"를 포함하는 모든 요소가 "front"의 값 배열에 들어가 있다
"java senior" -> "java senior"를 포함하는 모든 요소가 "java senior" 키-값 배열에 들어있다
query[i]의 문자열 키는 1~4개의 필드가 될 수 있다. 키가 "frontend"인 것만으로 "frontend"를 포함하는 모든 info 요소가 값-배열에 담겨 한번에 가져올 수 있도록 해시가 구성되어야 한다. 그럼 해시에 info를 저장할 때 키가 한번에 여러 요소를 가져올 수 있도록 설계한다.
info에서 문자 필드 4개의 경우의 수는 2^4이다. 해시에 16 X info.length 만큼 키를 만들면 되지 않을까? info 전체에 적용하면 O(n X 2^4) => O(n)이므로, info에 있는 모든 키의 조합을 저장하는 것이 가능하다. 해시 값에는 "frontend"인 모든 요소, "java frontend"인 모든 요소를 배열에 push한다. 중복이 생겨 공간 효율이 떨어지는 것 같지만, 쿼리가 선택적nullable이기 때문에 필요하다.
이로써 첫번째 조건의 구현 목표가 뚜렷해졌다. 이를 목표하여 모든 키의 조합을 키로 만드는 방법을 찾는다.
참고
info에서 문자 필드 4개의 경우의 수가 2^4인 이유
info[i]4가지 문자 필드의 모든 조합을 있거나("java")/ 없거나( "-")로 구분한다.query[i]는 해시에 저장된 키만 O(1)로 가져온다.
이게 문제의 함정으로 보인다. 언어 3개, 직군 2개, 경력 2개, 소울푸드 2개 - 필드가 가능한 숫자와 상관없이info[i]의 문자 필드는 not null이기에, 저장 단계에서 필터링이 가능하게 만든다.query[i]의 문자 필드는 "-"이거나 문자이다.
구현하기
function solution(info, query) {
// 0. Map을 사용한 탐색 저장소.
let map = new Map();
// 1. 저장 단계 : map에 저장하기 위한 함수.
// info[i]의 문자열 키로 가능한 모든 조합 등록 + 해당 키-값인 배열에 점수 추가.
// dfs가 사용되었다.
function updateMap (words, score, start, key){
if(start === words.length) { // key에 4개 단어가 완성됐을 때 키, 점수를 추가한다
if(!map.has(key)) {
map.set(key, [])
}
map.get(key).push(score)
return // 재귀 함수의 중단 조건
}
// dfs로 가능한 모든 조합을 만든다.
updateMap(words, score, start + 1, key + words[start]) // 첫 호출 시 첫 키가 'words[0]'
updateMap(words, score, start + 1, key + "-") // 첫 호출 시 처음 키는가 '-'
}
// 2. info를 map에 실제로 저장
for(let 지원자 of info) {
let words = 지원자.split(" ")
let score = Number(words.pop()); // 문자열로 저장된 숫자이니 변환한다.
updateMap(words, score, 0, '') // updateMap의 첫 호출은 빈 문자
}
// 3. map에 저장된 모든 키의 점수를 정렬한다.
for(let [_, scores] of map){
scores.sort((a,b) => a - b)
}
// 4. query의 O(n) 순회를 시작한다.
let result = [];
for(let q of query) {
let qArr = q.replace(/ and /g, " ").split(" ");
let qScore = Number(qArr.pop()) // X 이상인 조건을 숫자로 바꾼다.
let qKey = qArr.join("") // map에서 가져오기 위한 조합의 키
// 4-1 map에 없을 시 0을 추가하고 넘어간다.
if(!map.has(qKey)){
result.push(0)
continue
}
// 4-2 키를 찾을 시 두번째 탐색, 점수 별로 정렬한다.
let infoScores = map.get(qKey)
// 이진 탐색으로 qScore 이상인 점수만 남긴다.
let left = 0, right = infoScores.length
// right를 qScore와 가장 근접한 곳으로 옮기고, left로 점수 이하를 뺀다.
while(left < right) {
let mid = Math.floor((left+right) / 2)
if(infoScores[mid] >= qScore) {
right = mid
} else {
left = mid + 1
}
}
result.push(infoScores.length - left)
}
return result;
}15분의 제한 시간을 두고 풀었다.
풀기 전 과정은
손으로 코드를 적어가며 원리를 되새겼다.
처음 나의 추론 과정과 정답 추론 과정을 읽었다.
이 과정에서 코드를 암기하려 하지 않고, 추론 과정과 원리 이해에 집중했다.
3번까지 마친 후, 30~1시간 시간을 두고 처음부터 문제를 풀었다.
첫 번째 조건 - 해시 구조
핵심: 적절한 데이터 형태를 위해 도구를 사용하기
여기서 배운 사고 과정은 이렇다.
어떻게 해시를 설계할까
오답 추론에서는 이 질문에서 한번 더 구체화가 이루어지지 않았다. 단지 '키로 필터링하기'에만 집중했다.문자열 키를 사용해 바로 숫자 배열이라는 값을 얻을 수 있는 해시 구조는 무엇일까
정답 추론 과정에서 여기까지는 질문이 구체화되었다. 키가 문자가 되고, 값이 숫자배열이어야 한다-는 필요성을 인지했다.'무슨 알고리즘을 쓰면 키의 모든 조합을 맵에 저장할 수 있을까?'
마침내 필요한 질문까지 도달한 것 같다. 문자열 조합이라면 그래프 탐색이 적절하다.
이 문제에선 해시 구조를 위해 DFS 알고리즘을 사용한다. 처음 정답 코드를 봤을 때, 그저 코드를 이해한 정도였다. 답은 알아도, 답에 이르는 과정을 몰랐다. 즉 단계마다 어떤 질문이 필요한 지 몰랐다. 그동안 DFS 문제를 꽤 많이 풀었는데 여전히 어렵고, 활용을 잘 못하는 이유도 아직 이 사고 방식에 낯설기 때문인 것 같다.
두 번째 조건 - 탐색하기
핵심 : 제한 안에서 적절히 탐색하기
O(n) 반복문 내부에서 숫자를 걸러내야 하기 때문에, filter와 같은 메서드는 사용이 안된다. 포인터 두개를 움직여 가며 log N으로 해결한다. 실제로 해시 값 배열을 조회하는 것이 아니기 때문에 가능하다.
앞선 DFS 사용과 마찬가지로, 이 경우에도 '적절한 도구 선택'이라는 질문까지 사고 과정이 놓여진다면, 문제가 꽤나 분명하게 풀렸을 것 같다.
결론
알고리즘은 결국 문제 해결을 위한 도구이다. 단순히 해시를 공부하려 시작한 이 문제에서 dfs, 이진탐색까지 필요하게 될 지 몰랐다. 하지만 이 도구들은 해시를 구성하기 위해 사용할 수 있다. 해시는 키를 함수로 변환하여 값이 대응되게 저장하는 것이다. 문제가 요구하는 것은, 해시를 어떻게 설계할 것인가-다. 이 과정에서 함수 인자의 형태, 조건, 타입을 단서로 적절한 알고리즘을 사용해 해시에 저장하는 것이 핵심이다.
'어차피 JS 적절한 객체를 잘 쓰는 거 아닌가? 굳이 해시 개념이라는 게 필요하나?'라는 의문이 해소됐다.