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

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/132265#

프로그래머스

---

2. 내가 푼 방법

빅오 O(n)이라는 시간제한이 있었기 때문에, 이중 for문을 돌리게 되면 시간초과가 났다.

이중 for문 외에는 방법이 생각이 안 났기 때문에, 다른 분들의 코드를 이해한 후에 풀 수 있었다.

 

형이 가진 롤케이크를 동생에게 나눠준다고 접근하면 쉽다.

따라서 형이 가진 롤케이크를 Map<Integer, Integer>에 담았고, 동생에게 나눠주는 롤케이크를 Set<Integer>에 담았다.

첫 번째 for문은 형이 가진 롤케이크 토핑을 카운트해서 Map에 담는 과정이고, 두 번째 for문은 동생에게 나눠줌과 동시에 카운트한 토핑 개수가 0이 될 경우, Map에서 해당 토핑을 지워주면서 Map과 Set의 사이즈를 비교했다.

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/Programmers/blob/main/Solution_%EB%A1%A4%EC%BC%80%EC%9D%B4%ED%81%AC%EC%9E%90%EB%A5%B4%EA%B8%B0.java

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        
        Map<Integer, Integer> all = new HashMap<>();
        Set<Integer> set = new HashSet<>();
        
        for (int top : topping) {
            all.put(top, all.getOrDefault(top, 0) + 1);
        }
        
        for (int top : topping) {
            set.add(top);
            
            all.put(top, all.get(top) - 1);
            if (all.get(top) == 0) {
                all.remove(top);
            }
            
            if (all.size() == set.size()) answer++;
        }
        
        return answer;
    }
}

---

4. 결과 및 회고

자른다는 접근에 치우치다 보니까 나눠준다는 방법을 생각하지 못했던 것 같다.

그리고 동일한 자료형에 담아둔다는 생각을 깨부수는 문제였어서 다음에 다시 풀어봐야겠다.