[240419] 알고리즘 리부트 52일차 - 프로그래머스 롤 케이크 자르기 자바

앞쪽과 뒤쪽으로 방향으로 순회하면서 각 인덱스 별로 몇개의 종류를 가지는지 set에 담고 set의 크기를 새로운 배열에 각각 넣어줬다. 그리고 경계가 되는 연속되는 두 인덱스의 값이 같을 경우 answer에 더해주는 방식으로 구현했다. 처음에는 앞쪽으로만 토핑의 수를 세고 매번 남은 토핑 종류를 세려고 했지만 인덱스 옮길 때마다 반복문을 최악의 경우 백만번의 인덱스를 매번 돌아줘야 하기 때문에 시간 초과가 발생한다. 따라서 아래 코드 처럼 미리 양방향으로 토핑 수를 세어주자.

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        
        int len = topping.length;
        
        int [] order = new int[len];
        int [] reverseOrder = new int[len];
        
        // 앞과 뒤에서부터 센 토핑의 가짓 수를 Set을 이용해서 구하고
        HashSet<Integer> former = new HashSet<>(); 
        HashSet<Integer> latter = new HashSet<>(); 
        
        for(int t = 0; t < len; t++) {
            former.add(topping[t]);
            order[t] = former.size();      
            
            latter.add(topping[(topping.length-1)-t]);
            reverseOrder[(topping.length-1)-t] = latter.size();
        }
        
        for(int i = 0; i<len-1; i++){
            if(order[i]==reverseOrder[i+1]) answer++;
        }          
                
        return answer;
    }
    

}