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

롤케이크 자르기

문제링크

풀이

슬라이딩 윈도우 / 구현
1. 케이크 조각을 두명으로 나눠야 하는데, 토핑이 최대 10,000개 까지 가능하므로 int[] person1 = new int[10_001];로 토핑 개수를 표시할 array를 만든다.
2. topping1라는 변수를 만들어서 각 변수에 각 사람이 먹는 토핑의 종류의 수를 저장한다.
3. 모두 2번사람이 케이크를 먹는다고 가정해서 조건문을 통해 두번째 사람이 가지고 있는 토핑을 개수를 저장하고, 또한 person2에 각 토핑의를 저장한다.
4. 다시한번 전체 topping을 순회하면서 한 토핑씩 두번째 사람에게서 첫번째 사람에게 토핑을 전달하여 케이크를 자른다. 이를 통해 첫번째 사람의 array에는 토핑 수를 증가 시키고 두번째 사람의 array에는 토핑의 수를 감소 시킨다.

• topping1, topping2를 통해 각 사람이 가지고 있는 토핑 종류의 수를 계산한다.
• 만약 topping1 == topping2라면 문제의 조건에 해당하므로 answer를 증가시키고 최종적으로 answer를 리턴한다.

코드

class Solution {
    public int solution(int[] topping) {
        int answer = 0;

        int[] person1 = new int[10_001];
        int[] person2 = new int[10_001];
        int topping1 = 0;
        int topping2 = 0;
        for (int curTopping : topping) {
            if (person2[curTopping] == 0) {
                topping2++;
            }
            person2[curTopping]++;
        }

        for (int curTopping : topping) {
            if (person1[curTopping] == 0) {
                topping1++;
            }
            if (person2[curTopping] == 1) {
                topping2--;
            }
            person1[curTopping]++;
            person2[curTopping]--;

            if (topping1 == topping2) {
                answer++;
            }
        }

        return answer;
    }
}