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

문제

프로그래머스

 

알고리즘

해시맵

 

풀이

모든 토핑을 2번째 롤케이크가 가지고 있는 상태에서 시작하여

롤케이크의 토핑을 하나씩 1번째 롤케이크로 옮기면서 토핑 종류의 수를 비교한다.

 

각 롤케이크의 토핑을 해시맵을 이용하여 토핑 번호를 key로 해당 토핑 개수를 value 로 저장한다.

 

i번째 토핑을 롤케이크 2에서 1로 넘겨주기 때문에

map2의 i 에 대한 value를 1 감소시키고 map1의 i 에 대한 value를 1 증가시킨다.

이때 map2 의 value가 0이 되면 해당 토핑이 롤케이크2에 없는 것이므로 롤케이크2의 토핑 종류 수 count2를 1 감소시킨다.

마찬가지로 map1 의 value가 1이 되면 해당 토핑이 롤케이크 1에 추가된 것이므로 롤케이크 1의 토핑 종류 수 count1을 증가시킨다.

 

위 과정으로 토핑 하나를 옮기고, count1과 count2가 동일하다면 answer를 1 증가시킨다.

 

코드

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        
        Map<Integer, Integer> cake1 = new HashMap<>();
        Map<Integer, Integer> cake2 = new HashMap<>();
        for(int t: topping)
            cake2.put(t, cake2.getOrDefault(t, 0) + 1);
        
        int count1 = 0;
        int count2 = cake2.keySet().size();
        
        for(int t: topping) {
            cake2.put(t, cake2.getOrDefault(t, 0) - 1);
            cake1.put(t, cake1.getOrDefault(t, 0) + 1);
            
            if(cake2.get(t) == 0) count2--;
            if(cake1.get(t) == 1) count1++;
            
            if(count1 == count2) answer++;
        }        
        return answer;
    }
}