프로그래머스 LEVEL 2(롤케이크 자르기)

사용 언어 : javascript
해결 날짜 : 2022-10-29
해결 방법 :
- 입력이 1000000 이하이므로 O(NlogN) 시간 이내에 풀어야함
- 끝에서부터 원소의 개수를 하나씩 제거하기 위한 Map()과 앞에서부터 원소를 하나씩 추가하기 위한 Set() 사용
- topping을 돌며 map에 모든 topping 별 개수 추가
- topping을 돌며 map에서 현재 topping의 개수를 1 감소 및 set에 현재 topping 값 추가
  - 이 때 topping의 개수가 0이 되면 사이즈 비교를 위해 map에서 삭제
  - set의 크기와 map의 크기가 같다면 공평하게 토핑을 나눠가질 수 있다는 뜻이므로 answer 1 추가
회고 :
- 처음에 set 두 개를 활용하여 하나는 앞에서부터, 다른 하나는 뒤에서부터 인덱싱하여 비교를 수행하였다.
- 그러다보니 정답을 증가시켜야 할 조건을 찾기 힘들어서 뒤에서부터 인덱싱하는 자료구조를 map으로 변경하였다.

코드

function solution(topping) {
    let answer = 0;
        
    const map = new Map();
    const set = new Set();
        
    for (const top of topping) {
        map.has(top) ? map.set(top, map.get(top) + 1) : map.set(top, 1);
    }

    for (const top of topping) {
        map.set(top, map.get(top) - 1);
        set.add(top);
        if (!map.get(top)) map.delete(top);
        if (set.size === map.size) answer++;
    }
        
    return answer;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges