링크

문제 링크

문제 설명

제한사항

입출력 예

입출력 예 설명

풀이

1. 배열 길이 제한이 1,000,000이다? O(n)에 끝내도 되더라 (뇌피셜)
2. 자료구조는 Map<Integer, Integer>를 선언해서 어떤 숫자가 몇 번 나왔는지 저장한다. 핵심은 map의 size!
3. O(n)믿고 처음에 형한테 케이크를 다줬다. (put)
4. 그리고 동생한테 하나씩 주면서 토핑 종류의 개수라고 할 수 있는 map의 size를 비교한다.
5. 같으면 answer++

나는 한글 변수 선언이 가능하게끔 된게 풀때도 좀 더 편한것같다 ㅋㅋㅋ

코드

import java.util.*;
class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        Map<Integer, Integer> 형 = new HashMap<Integer, Integer>();
        Map<Integer, Integer> 동생 = new HashMap<Integer, Integer>();        
        for(int i = 0; i < topping.length; i++) 
        {
            형.put(topping[i], 형.getOrDefault(topping[i], 0) + 1);
        }
        for(int cut = 1; cut < topping.length; cut++)
        {
            동생.put(topping[cut - 1], 동생.getOrDefault(topping[cut - 1], 0) + 1);
            형.put(topping[cut - 1], 형.get(topping[cut - 1]) - 1);
            if(형.get(topping[cut - 1]) == 0) 
            {
                형.remove(topping[cut - 1]);
            }
            if(동생.size() == 형.size())
            {
                answer++;
            }
        }
        
        return answer;
    }
}