[프로그래머스] 롤케이크 자르기

코드 힌트

1. 문제 이해하기:
   • 이 문제의 핵심은 롤케이크를 자를 때, 두 부분에 있는 토핑 종류의 수가 동일한 경우를 찾는 것입니다.
   • 롤케이크의 크기나 각 부분의 토핑 개수는 중요하지 않고, 오직 각 부분에 포함된 고유한 토핑 종류의 수가 중요합니다.
   • 예를 들어, [1, 1, 1, 1]이 주어졌을 때, 다음과 같은 세 가지 경우가 가능합니다:
     • [1] [1, 1, 1]
     • [1, 1] [1, 1]
     • [1, 1, 1] [1]
2. 자료구조 선택하기:
   • 저는 이 문제를 효율적으로 풀기 위해, HashMap을 사용하여 각 부분에 포함된 토핑의 종류와 개수를 추적했습니다.
   • HashMap의 key에는 토핑의 종류, value에는 해당 종류의 토핑 개수를 저장합니다.
   • 처음에는 HashSet을 사용하여 각 부분의 고유한 토핑을 추적하려고 했지만, 2중 for문을 사용하게 되어 시간 초과 문제가 발생했습니다.
3. 2중 반복문을 피하기 위해 포인트 사용:
   • 두 개의 HashMap을 선언하여 각각 두 부분의 토핑 종류를 관리합니다.
   • 처음에는 map1에 첫 번째 토핑 요소만 저장하고, map2에는 나머지 토핑 요소들을 모두 저장합니다.
   • 그런 다음, point 변수를 사용하여 배열을 순차적으로 탐색하면서, map1에 현재 포인트의 토핑을 추가하고, map2에서는 해당 토핑을 제거합니다.
   • 만약 map2에서 특정 토핑의 개수가 0이 되면, 그 토핑을 map2에서 제거합니다.
4. 조건에 맞는지 확인하기:
   • 배열을 탐색하면서, 각 지점에서 map1.size()와 map2.size()를 비교합니다.
   • 만약 두 HashMap의 크기가 같다면, 두 부분에 포함된 고유한 토핑의 수가 동일한 것이므로, 정답 변수에 +1을 합니다.
   • 그런 다음 point를 증가시켜 다음 지점으로 이동합니다.

 

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int result = 0; // 조건을 만족하는 경우의 수를 저장하는 변수
        
        // 첫 번째와 두 번째 파트를 각각 추적하는 HashMap 초기화
        HashMap<Integer, Integer> map1 = new HashMap<>(); // 첫 번째 파트의 토핑 개수를 저장
        HashMap<Integer, Integer> map2 = new HashMap<>(); // 두 번째 파트의 토핑 개수를 저장
        
        int n = topping.length;
        
        // 첫 번째 토핑을 map1에 추가
        map1.put(topping[0], 1);
        
        // 나머지 토핑들을 map2에 추가
        for (int i = 1; i < n; i++) {
            map2.put(topping[i], map2.getOrDefault(topping[i], 0) + 1);
        }
        
        int point = 1; // 두 파트를 구분하는 지점 초기화
        
        // 두 파트의 크기를 비교하며 반복
        while (point < n - 1) {
            if (map1.size() == map2.size()) {
                result++; // 두 파트의 크기가 같을 때 경우의 수 증가
            }
            
            int key = topping[point]; // 현재 토핑
            
            // 현재 토핑을 첫 번째 파트에 추가
            map1.put(key, map1.getOrDefault(key, 0) + 1);
            
            // 두 번째 파트에서 현재 토핑을 제거 (또는 개수를 감소)
            if (map2.get(key) == 1) {
                map2.remove(key);
            } else {
                map2.put(key, map2.get(key) - 1);
            }
            
            point++; // 다음 토핑으로 이동
        }
        
        return result; // 조건을 만족하는 경우의 수 반환
    }
}