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

😥 1번째 시도 : 시간초과

import java.util.*;
class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        List<Integer> p1 = new ArrayList<>();
        
        for(int i = 0 ; i < topping.length; i++){
            if(!p1.contains(topping[i]))
                p1.add(topping[i]);
            List<Integer> p2 = new ArrayList<>();
            
            for(int j = i+1 ; j < topping.length; j++){
                if(!p2.contains(topping[j]))
                    p2.add(topping[j]);
                
                if(p1.size() < p2.size())
                    break;
                
                if(j == topping.length-1 && p1.size() == p2.size())
                    answer++;
            }
        }
        
        return answer;
    }
}

🤔 2번째 시도 : 시간초과

이 전보다는 낫지만 여전히 효율성이 떨어진다.

import java.util.*;
class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        int[] p1 = new int[10001];
        int p1_cnt = 0;
        
        for(int i = 0 ; i < topping.length; i++){
            if(p1[topping[i]] == 0){
                p1_cnt++;
                p1[topping[i]] = 1;
            }
                
            int[] p2 = new int[10001];
            int p2_cnt = 0;
            for(int j = i+1 ; j < topping.length; j++){
                if(p2[topping[j]] == 0){
                    p2_cnt++;
                    p2[topping[j]] = 1;
                }
                
                if(p1_cnt < p2_cnt)
                    break;
            }
            
            if(p1_cnt == p2_cnt)
                answer++;
        }
        
        return answer;
    }
}

---

💡 해결

결국 1시간 이상 고민하다가 더는 안되겠다 싶어서 풀이를 참고..
대부분 해시맵을 이용해서 풀이를 하셨고 나는 해시맵,셋 에 대해서 깊게 알고 있지 않아서 두 가지에 대해서 먼저 공부했다!

해시Map 알아보기 [JAVA]

해시Set 알아보기 [JAVA]

---

문제를 해결하기 위해서 흐름을 보자!
우리가 구하고 싶은 건 결국 반으로 나누었을 때 같은 종류를 가지는 순간이 언제고 그 상황들이 몇 번 발생했는지를 알고 싶은거다!

그렇다면 배열을 반으로 나누면서 각 공간의 종류를 체크하면 되는 일이다.
이를 위해서 우리가 어떻게 구현할 수 있을까?

가장 쉽게 생각하는 방법은 내가 1,2번째에서 생각하고 퇴짜를 맞는 배열 2개를 이용해서 푸는 방법이다. 이렇게 문제를 풀고 시간초과를 겁나 맞아보면 효율적 측면에서 이 방법은 아니라는 생각이 들텐데 이 때 우리는 Hash를 사용한다!

---

🤷‍♂️왜 Hash를 써?

많은 곳을 찾아보면서 해쉬맵,해쉬셋을 사용해야하는 건 알겠는데 왜 사용하는지는 자세히 적혀있지 않았다. 그만큼 내가 부족하다는 의미이다.

차근차근 처음부터 짤라가면서 우리는 모든 경우를 확인해보자.
첫번째 1, 두번째 2 1 3..
두번째 1 2 두번째 1 3 ..
세번째 1 2 3 두번째 3 ..

계속 나눠가면서 보이는 건

첫번째 배열을 계속 증가(add) 두번째 배열은 하나씩 out(remove)

추가로 중복되는 숫자는 포함하지 않는다

이 2가지를 집중해본다면 계속 증가하면서 숫자를 포함하지 않는 자료형은 Set이고 우리는 해쉬를 적용하여 더욱 빠른 HashSet을 사용하는 것이 더욱 이점을 가진다.

또한 두번째 배열은 하나씩 remove할 수 있어야하고 마찬가지로 중복된 숫자는 포함하지 않아야한다. 여기서 똑같이 Set을 사용하여 Set 2개를 이용하여 풀이를 할 수 있지 않나라는 생각이 들었는데, 중복이 존재하기 때문에 예를 들어 2 3 4 5 2에서 2를 제거한다고 하면 2를 두 번 제거하는 상황이 일어나서 차라리 등장한 횟수까지 같이 저장할 수 있는 HashMap을 사용하는 것이 구현하기 편하다.

---

💻구현

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        int size = topping.length;
        
        HashSet<Integer> first = new HashSet<>();//순서없고 중복된 거 저장 안하는 배열
        HashMap<Integer, Integer> second = new HashMap<>();//키,값 
        
        first.add(topping[0]);
        //1~전체 해시맵에 집어넣고 이미 존재한다면 +1
        for (int i = 1;i < size; i++) {
            second.put(topping[i], second.getOrDefault(topping[i], 0) + 1);
        }
        
        //1~전체 해시맵 순회
        for (int i = 1;i < size; i++) {
            first.add(topping[i]);//해시Set에 넣기(이미 있다면 안 넣는다)
            second.put(topping[i], second.get(topping[i]) - 1);//이미 넣은 값들에서 -1
            if (second.get(topping[i]) == 0) {//-1해서 0이라면 맵에서 제거하자
                second.remove(topping[i]);
            }
            if (first.size() == second.size())
                answer++;
        }
        return answer;
    }
}