◼️ 문제
1. 문제 설명
2. 제한사항
3. 입출력
◼️ 풀이
✏️ 전반적인 풀이과정
- 토핑 소유 내역을 기록할 2개의 Map 객체를 생성한다.
- 토핑을 한 사람이 전부 소유했다는 가정하에, topping 배열을 순회하며 토핑 정보를 A의 Map에 전부 넣어준다.
- topping 배열을 차례대로 순회하며 현재 인덱스의 토핑을 B에게 넘겨준다.
3-1. 현재까지 A와 B의 토핑 종류 개수가 같다면 count를 늘리고, isFind(균등 분배 시작 여부)를 true로 만든다.
3-2. A와 B의 토핑 종류 개수가 다르고, 아직 균등 분배를 시작하지 않았다면 다음 인덱스로 이동한다.
3-3. A와 B의 토핑 종류 개수가 다르고, 균등 분배를 시작했던 이력이 있다면 순회를 종료한다. - 결과를 반환한다.
📃 풀이과정 추가 설명
토핑 관리 방식
위에 설명했다시피 일단 A라는 사람에게 토핑을 몽땅 몰아주었다는 가정에서 시작했다.
인덱스 순서대로 하나씩 B에게 토핑을 넘겨주면서 토핑 종류 개수가 일치하는 시점을 찾겠다는 아이디어다.
isFind 변수 사용 이유
내가 가장 핵심적인 아이디어라고 생각했던 점이 순회를 중간에 멈출 수 있는 조건이었다.
2개 이상의 방식으로 토핑을 균등 분배할 수 있는 경우라면 그 경우는 연속된 상황일 것이라는 점이다.
A가 B에게 토핑을 넘겨주는 순간 A의 토핑 종류는 줄어들거나 유지할 것이다. 절대 늘어나지 않는다.
A가 B에게 토핑을 하나씩 넘겨주면서 토핑 종류가 균등 분배된 케이스를 발견하는 순간부터
A의 토핑 개수가 감소하기 직전까지가 count 대상인 것이다.
isFind가 false라면 아직 균등 분배는 시작도 안한 것이니 계속 토핑을 넘겨주고,
isFind가 true라면 균등 분배를 시작한 것인데, 토핑 종류 개수가 다르면 유효한 범위가 종료되었음을 의미한다.
😓 헤맸던 이유
Map 객체가 그렇게 좋은지 몰랐다..
처음에는 토핑 종류를 저장하는 객체를 일반 Object 객체로 만들어 풀었다.
그런데 계속해서 시간초과가 발생했다.
해시를 구현할 땐 Object 말고도 Set과 Map이 있다는 것을 알고 있었지만,
Set의 경우 내가 원하는 로직(토핑 종류와 개수 모두 카운트)을 구현할 수 없어 배제했다.
Map은 key와 value로 이루어진 구성이라는 게 Object와 어떤 차이가 있는지도 모르겠고,
값을 추가하거나 수정하는 과정이 나에겐 다소 복잡하고 낯설게 느껴져서 필요성을 못 느끼고 있었다.
계속 해도 안되길래 답답한 마음에 급하게 Map을 사용하는 방법을 알아보고 적용해봤는데
바로 해결이 되었다... (허무ㅠ)
그렇다면 Object보다 Map이 더 효율적이라는건데 이유가 뭘까?
Map과 Object를 비교할 때 서로 장단점이 있는 것 같지만 가장 주목할 점은 이것 같다.
- Object
- 키-값 조작이 Map보다 성능이 낮다.
- 프로토타입 체인 탐색으로 인해 부가 비용 발생할 수 있다.
- Map
- 키-값의 삽입, 삭제, 탐색이 Object보다 성능이 더 좋다.
- 특히 대용량 데이터 처리에 최적화된 성능을 가지고 있다.
평소에 내가 풀었던 문제들은 굳이 Map을 사용하지 않아도 해결되는 것들이었나보다.
Map 다루는 게 어색해서 잘 안 사용했는데 이제라도 좀 고쳐먹고
Map도 적극적으로 다뤄서 문제를 해결해보겠다.
💻 코드
function solution(topping) {
let count = 0;
const person1 = new Map();
const person2 = new Map();
topping.forEach((num) => person1.set(num, (person1.get(num) || 0) + 1));
let isFind = false;
for (let i = 0; i < topping.length; i++) {
person1.set(topping[i], person1.get(topping[i]) - 1);
person2.set(topping[i], (person2.get(topping[i]) || 0) + 1);
if (person1.get(topping[i]) === 0) person1.delete(topping[i]);
if (person1.size === person2.size) {
count++;
isFind = true;
} else if (isFind && person1.size != person2.size) {
break;
}
}
return count;
}