롤케이크 자르기

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

프로그래머스

 

문제 풀이

 처음에는 케이크를 반절로 나눈 뒤, 오른쪽 Set, 왼쪽 Set을 만든 뒤, Set이 큰 쪽으로 인덱스를 옮기면서 두 SET의 크기가 같은 경우를 세는 방법으로 작성할까 생각했었다. 하지만 이 방법도 결국 O(N^2)의 시간 복잡도를 가져, 타임오버가 날 것 같아서 다른 방법을 생각해봤다.

 토핑을 오른쪽에서 왼쪽으로 하나씩 옮기면서 토핑의 종류가 같은 경우를 카운팅하는 방법을 생각해냈다. 그러려면 케이크의 왼쪽과 오른쪽에 있는 토핑의 종류와 숫자를 저장해야 하므로 Set이 아니라 Map으로 구현해야 한다.

 

 

작성한 코드 (정답)

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int solution(int[] topping) {        
        int answer = 0;
        
        // 롤케이크의 왼쪽 오른쪽 Map 생성
        Map<Integer,Integer> left = new HashMap<>();
        Map<Integer,Integer> right = new HashMap<>();
       
        // 왼쪽->오른쪽 방향으로 케이크를 자를 것이기 때문에 오른쪽에 토핑 모두 저장
        for (int top : topping) {
            right.merge(top,1,Integer::sum);
        }

        // 왼쪽->오른쪽 방향으로 케이크를 자르면서 토핑을 하나씩 옮기면서   
        // 토핑 종류가 왼쪽 == 오른쪽인 경우를 카운팅
        for (int top : topping) {
            left.merge(top,1,Integer::sum);

            right.merge(top,-1,Integer::sum);
            if (right.get(top) == 0) {
                right.remove(top);
            }
                        
            if (left.size() == right.size()) answer++;
        }
        
        return answer;
    }
}