Lv.2 : 롤케이크 자르기

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 배열에 특정 부분을 잘라 나오는 두 집합의 원소 종류 수가 같은 경우의 수를 반환한다.

🔸 문제 풀이 🔸

• 순서대로 한 인덱스씩 잘라보며 계산한다.
• 토핑을 인덱스로 구분해 카운트하고, 1이상인 원소들의 수를 카운트로 따로 계산한다.
• 두 집합의 원소 카운트가 같은 경우의 수를 반환한다.

---

🔸 코드 🔸

class Solution {
    public int solution(int[] topping) {
        // Input
        int[] t1 = new int[10_001];
        int[] t2 = new int[10_001];
        int cnt1 = 0;
        int cnt2 = 0;

        for (int t : topping) {
            if (++t2[t] == 1)
                cnt2++;
        }

        // Check
        int answer = 0;

        for (int i = 0; i < topping.length-1; i++) {
            int idx = topping[i];
            if (++t1[idx] == 1) cnt1++;

            if(--t2[idx] == 0) cnt2--;

            if (cnt1 == cnt2) answer++;
        }

        // Output
        return answer;
    }
}

🔸 코드 해석 🔸

• 각 집합의 원소 개수를 int배열 t1, t2에 카운트하고, 원소의 종류 수를 cnt1, cnt2로 카운트한다.
• t1, t2의 한 인덱스의 값이 1, 0이 될때 카운트를 변화한다.
• 두 카운트 cnt1, cnt2의 값이 같을때의 수를 answer에 카운트 후 반환한다.

---

🔸 end 🔸

• 원소 수를 카운트하고, 종류를 따로 카운트하는 아이디어만 있다면 쉽게 풀 수 있었던 것 같다.
  • 원소의 수 카운트를 Map으로 해서 종류 카운트를 편하게 할 까 했지만, 원소 종류가 자주 생기고 지워지면 연산이 오히려 느려질 것 같아서 전체 토핑 범위 만큼 배열 크기를 만들어 사용했다.