[프로그래머스/Lv. 2] 롤케이크 자르기 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public int solution(int[] topping) {
        int answer = 0; // 롤케이크 공평하게 자르는 방법의 수
        
        Set<Integer> set1 = new HashSet<>();    // 형
        Map<Integer, Integer> map2 = new HashMap<>();    // 동생
        
        for(int t : topping) {
            map2.put(t, map2.getOrDefault(t, 0) + 1);
        }
        
        for(int t : topping) {
            // 형은 원소를 추가한다.
            set1.add(t);
 
            // 동생은 원소를 뺀다.
            map2.put(t, map2.get(t) - 1);
            if(map2.get(t) == 0) { // 원소를 뺐을 때 값이 0이면, Map에서 제거
                map2.remove(t);
            }
            
            // 가짓수가 같다면, 정답 + 1
            if(set1.size() == map2.size()) {
                answer++;
            }
        }
                
        return answer;
    }
}

 

 

🧩  해결 아이디어

• HashSet + HashMap

- 시간 복잡도 : O(N)

 

1_ 일단 반복문을 돌며 동생의 Map에 토핑 종류와 갯수 <Integer, IntegeR>를 추가한다.

 

2_ 한 번 더 반복문을 돌며, 형의 Set에는 토핑 원소를 추가하고, 동생의 Map에는 토핑 원소 갯수를 뺀다.

이 때, 빼고 난 후 동생의 토핑 원소 갯수가 0개라면, Map에서 해당 값을 제거한다.

 

"형의 토핑 원소 갯수 = 동생의 토핑 원소 갯수"라면 정답 + 1을 한다.

 

 

 

---

🔺 다른 풀이들

- HashSet 하나랑 int형 배열 활용해 푸셨다.(좀 더 빠름)

[프로그래머스] lv2 롤케이크 자르기(JAVA)

 

- Map만 2개 써도 된다.

---

💬 느낀 점

첨에 Set 2개 만들어서 해보려다가 시간 초과 떠가지고 (아무래도 1,000,000에 O(N^2)이니까..)

다른 방법 찾아보고 했다...

 

어려운 문제는 아닌데 아이디어 생각이 안 나는 것이 아숩다 ..ㅠ

Set 과 Map을 조합해 쓸 줄이야.. 뇌를 말랑하게 만들좌,,,,,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[JAVA] LV2. 롤케이크 자르기

 

[연습문제] 롤케이크 자르기 - JAVA