Hash 2 - 적용과 응용
2025/02/25
n°59
category : Data Structures & Algorithms
☼
2025/02/25
n°59
category : Data Structures & Algorithms
탐색 영역과 비교군을 명확히 하기
단계를 나누고, 적절한 도구를 선택하기
타입과 조건에서 단서 찾기
이 글의 목적은 암기하는 게 아니라 *사고 과정 자체를 학습하기이다.
지난 글에 이어 해시를 알아본다. 이번엔 처음 풀어본 문제로 사고 과정과 실패 원인, 동작 원리를 분석했다. 제한 시간 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, query O(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으로 만들고 부분집합 여부로 갯수를 확인.
하지만...