[프로그래머스|JAVA] 롤케이크 자르기 | Set과 Map 사용 ⭕️ | Set 과 Map 특징 및 시간 복잡도 비교 | 실패한 코드도 같이..📚

[문제 링크]

프로그래머스

 

[문제]

 

---

 

📍 [코드]

import java.util.*;
class Solution {
    // Map → 원소별 개수까지 관리 가능 (사실상 Set + 카운터) 
    // Set 두번 쓸 때보다 시간 복잡도 효율적
    public int solution(int[] topping) {
        int answer = 0;
        
        Map<Integer, Integer> right = new HashMap<>();
        Set<Integer> left = new HashSet<>();
        
        // 모든 토핑이 오른쪽에 추가
        for (int t : topping) {
            // getOrDefault() + 1 -> 카운트 기능
            right.put(t, right.getOrDefault(t, 0) + 1);
        }
        
        // 왼쪽에 추가하며 오른쪽에서 원소 카운트 수 감소
        for (int t : topping) {
            left.add(t);
            
            right.put(t, right.get(t) - 1);
            if (right.get(t) == 0) {
                right.remove(t);
            }

            if (left.size() == right.size()) {
                answer++;
            }
        }
        
        return answer;
    }

 

💡 접근법

• 오른쪽 토핑을 담을 Map과 왼쪽 토핑을 담을 Set을 활용
• 오른쪽에 모든 토핑을 추가할 때,
  • getOrDefault() + 1를 활용하여 카운팅도 함께 진행
• 왼쪽에 토핑을 추가하며, 오른쪽 토핑 카운팅 차감
  • 이때, 토핑이 없다면 제거한다. (즉, 카운트 = Value = 0)
  • 왼쪽(Set)과 오른쪽(Map)의 사이즈가 같다면 공평하게 나눠진 것이므로 카운트한다. (즉, answer++)

 

✅ Map→ 원소별 개수까지 관리 가능 ( 사실상 Set + 카운터 )

⏳  시간 복잡도 : O(n)

---

처음엔,, 중복 제거가 핵심이라 생각하고 시간복잡도를 고려하지 않고 Set만 사용하였다.
결국 O(n^2)으로 시간 초과 맞아서 당황했다.. 😅
실패 또한 중요한 경험이므로 실패한 코드도 첨부하겠다.

📍 [실패 코드 - 시간 초과]

import java.util.*;
class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        
        for(int i = 1; i <= topping.length; i++){
            if(check(i, topping)) answer++;
        }
        
        return answer;
    }
    
    public boolean check(int num, int[] arr) {
        // Set 특징 - 중복 제거 활용
        // O(n^2)
        Set<Integer> set = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        
        for(int i = 0; i < arr.length; i++){
            if(i <= num) set.add(arr[i]);
            else set2.add(arr[i]);
        }
        
        return set.size() == set2.size() ? true : false;
    }
}

 

---

 

💬 마무리

문제를 보자마자 Set을 활용한 방법밖에 생각나지 않았고,
그 생각에만 갇혀 새로운 방식을 떠올리기까지 오랜 시간이 걸렸다..
항상 넓은 시야로 넓게 생각하자 다짐하지만 역시 쉽지 않은 것 같다 😅
그래도 이 문제로 인해 시간 복잡도에 대해 생각해보고 Map의 특징도 다시 한 번 짚고 넘어가서
좋은 문제인 것 같다.