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

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

처음 코드

이 코드는 index값을 이용하여 형과 동생의 hashMap에 토핑을 넣고, map의 개수를 다져 개수를 구해주도록 한 코드이다.

형에게 토핑을 추가하는 것은 한 번의 단계에서 한 단계씩 이루어지기 때문에 상관이 없다(i에서 형에게 추가 하고, 동생을 전부 추가한 뒤 다시 형에게 i+1을 추가하기 때문). 하지만, 동생의 경우에는 형의 i에 따라서 계속 달라지는 값이기 때문에 매번 초기화를 해 주어야 한다.

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        HashSet<Integer> bigBro = new HashSet<>();
        int answer = 0;
        for(int i=0; i<topping.length; i++){
            bigBro.add(topping[i]); //형에게 모든 토핑 추가
            HashSet<Integer> littleBro = new HashSet<>();
            for(int j=i+1; j<topping.length; j++){
                littleBro.add(topping[j]);
            }
            if(littleBro.size() == bigBro.size()){
                answer ++;
            }
        }
        return answer;
    }
}

정답 코드

이 문제는 시간복잡도를 낮게 하는 것이 목표이므로, 시간복잡도가 O(n^2)인 HashSet 말고 O(n)인 HashMap을 사용해 주어야 한다.
(HashSet의 시간복잡도 : O(n), HashMap의 시간복잡도 : O(n))

이후, for문을 이용하여 현재 지점의 토핑을 추가하고, 반대쪽에서 제거하는 방식으로 진행하면 된다. 즉, 한 곳에 전부 채워 둔 후 반대쪽에 현재 토핑을 추가하고, 전부 채워둔 곳에서 제거하는 식으로 진행하면 되는 것이다.

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        HashMap<Integer, Integer> big = new HashMap<>();
        HashMap<Integer, Integer> little = new HashMap<>();
        int answer = 0;
        int length = topping.length;
        
        for (int i = 0; i < length; i++) {
            if (little.containsKey(topping[i])) {
                little.put(topping[i], little.get(topping[i]) + 1);
            } else {
                little.put(topping[i], 1);
            }
        }

        for (int j = 0; j < length - 1; j++) {
            int current = topping[j];
            
            if (big.containsKey(current)) {
                big.put(current, big.get(current) + 1);
            } else {
                big.put(current, 1);
            }
            
            if (little.containsKey(current)) {
                int count = little.get(current);
                if (count == 1) {
                    little.remove(current);
                } else {
                    little.put(current, count - 1);
                }
            }

            if (little.size() == big.size()) {
                answer++;
            }
        }

        return answer;
    }
}