[132265] 롤케이크 자르기

✔ 롤케이크 자르기

[프로그래머스 132265]

문제 분석하기

두 개의 해시맵을 사용해 해시맵1에 케이크를 모두 저장한 후,

해시맵2에 하나씩 나누어 주면서 두 해시맵의 크기가 동일할 경우 공평하게 잘라지게 됨

손으로 풀어보기

1. cake2 해시맵에 모든 토핑 저장
2. cake2 해시맵에서 토핑 하나를 삭제하고 cake1에 저장
3. cake1과 cake2의 토핑 갯수가 동일한지 확인
   • 동일하다면 공평하게 잘라지므로 공평하게 자르는 방법의 수 증가
4. 공평하게 자르는 방법의 수를 반환

슈도코드 작성하기

topping(롤케이크에 올려진 토핑들의 번호)
answer(롤케이크를 공평하게 자르는 방법의 수)
cake1(앞의 케이크 조각의 토핑 종류와 갯수를 담은 HashMap)
cake2(뒤의 케이크 조각의 토핑 종류와 갯수를 담은 HashMap)
for(t -> topping만큼) {
    cake2에 모든 topping 저장
}
for(t -> topping만큼) {
    cake2에서 t 삭제
    cake1에 t 추가
    if(cake1의 크기와 cake2의 크기가 같다면)
        cake1과 cake2의 토핑 종류의 갯수가 같으므로 answer 증가
}
answer 반환

코드 구현하기

/**
 * 132265) 롤케이크_자르기
 */
public class L082_132265 {
    // topping(롤케이크에 올려진 토핑들의 번호)
    public int solution(int[] topping) {
        // answer(롤케이크를 공평하게 자르는 방법의 수)
        int answer = 0;
        // cake1(앞의 케이크 조각의 토핑 종류와 갯수를 담은 HashMap)
        Map<Integer, Integer> cake1 = new HashMap<>();
        // cake2(뒤의 케이크 조각의 토핑 종류와 갯수를 담은 HashMap)
        Map<Integer, Integer> cake2 = new HashMap<>();
        // cake2에 모든 topping 저장
        for (int t : topping) {
            cake2.put(t, cake2.getOrDefault(t, 0) + 1);
        }
        for (int t : topping) {
            // cake2에서 t 삭제
            if (cake2.get(t) - 1 == 0)
                cake2.remove(t);
            else
                cake2.put(t, cake2.get(t) - 1);
            // cake1에 t 추가
            cake1.put(t, cake1.getOrDefault(t, 0) + 1);
            // cake1의 크기와 cake2의 크기가 같다면
            if (cake1.size() == cake2.size())
                // cake1과 cake2의 토핑 종류의 갯수가 같으므로 answer 증가
                answer++;
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L082_132265 solution = new L082_132265();

        int[] topping = { 1, 2, 1, 3, 1, 4, 1, 2 };

        int result = solution.solution(topping);

        System.out.println(result);
    }
}