[Programmers] 롤케이크 자르기 / ❌

프로그래머스

 

1. 제출 코드 (1시간 5분 20초 / 맵)

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        HashMap<Integer, Integer> m1 = new HashMap<>();
        HashMap<Integer, Integer> m2 = new HashMap<>();
        
        m1.put(topping[0], 0);
        
        for(int i = 1; i < topping.length; i++) {
            m2.put(topping[i], m2.getOrDefault(topping[i], 0) + 1);
        }
        
        for(int i = 1; i < topping.length; i++) {
            if(m1.size() == m2.size()) {
                answer++;
            }
            m1.put(topping[i], m1.getOrDefault(topping[i], 0) + 1);
            
            if(m2.get(topping[i]) != null) {
                if(m2.get(topping[i]) - 1 == 0){
                    m2.remove(topping[i]);
                } else {
                    m2.put(topping[i], m2.get(topping[i]) - 1);
                }
            }
        }
        return answer;
    }
}

 

2. 구현 로직

1. Map 2개를 만들고 map1에 topping 1개를 삽입, map2에는 그 외 토핑을 모두 삽입
2. 2번째 topping부터 탐색 진행
   1. 만약, map1과 map2의 size가 같다면 answer++
   2. map1에 현재 토핑이 있다면 value + 1
   3. map2에 현재 토핑이 있을 때, value - 1을 하는데 0이되면 제거

 

3. 회고

• HashSet을 이용해서 처음에 풀었는데 시간 복잡도가 N^2으로 풀리지 않았다. 사실 알고 있었는데 그냥 다른 방법이 생각나지 않아서 시도해보았다.
• 이전에도 동일한 경우가 있었는데 그때 다시는 이런식으로 문제를 풀지 않기로 다짐했지만 맘처럼 그게 되지 않는다.