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

문제

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

프로그래머스

접근 방법 및 풀이

처음 생각한 방법은 topping 배열을 1번째 인덱스부터 topping length - 1까지 기준을 이동하면서 배열을 앞쪽과 뒷쪽으로 배열을 복사하고 각 배열을 Set에 추가하여 중복을 제거 후 각 Set의 길이를 비교하여 동일 한지 비교

import java.util.Arrays;
import java.util.Set;
import java.util.stream.Collectors;

public class Q30_132265 {
    /**
     * 효율성 통과하지 못함
     */
    public int solution(int[] topping) {
        int answer = 0;

        int length = topping.length;
        for (int i = 1; i < length - 2; i++) {
            int[] topping0 = Arrays.copyOfRange(topping, 0, i);
            int[] topping1 = Arrays.copyOfRange(topping, i, length);
            Set<Integer> set0 = Arrays.stream(topping0).boxed().collect(Collectors.toSet());
            Set<Integer> set1 = Arrays.stream(topping1).boxed().collect(Collectors.toSet());
            if (set0.size() == set1.size()) {
                answer++;
            }
        }

        return answer;
    }
}

채점의 테스트 케이스는 정확성 항목만 있지만 대부분 실행 시간을 초과

배열을 복사하고 int를 Integer로 변환하는 과정에서 성능 저하가 발생할 것이으로 추측

배열을 복사하지 않고 롤케익을 나누는 기준을 옮기면서 토핑의 종류 만큼 선언한 boolean 배열에 종류를 확인해 가면서 형의 롤케익 부분과 동생의 롤케익 부분의 토핑의 종류를 확인

public class Q30_132265 {
    /**
     * 효율성 통과하지 못함
     */
    public int solution(int[] topping) {
        int answer = 0;

        int length = topping.length;
        for (int i = 1; i < length - 2; i++) {
            int size0 = this.getTypeSize(topping, 0, i);
            int size1 = this.getTypeSize(topping, i + 1, length - 1);
            if (size0 == size1) {
                answer++;
            }
        }

        return answer;
    }

    public int getTypeSize(int[] topping, int start, int end) {
        int size = 0;
        boolean[] booleans = new boolean[10000];
        for (int index = start; index <= end; index++) {
            int number = topping[index];
            if (!booleans[number - 1]) {
                booleans[number - 1] = true;
                size++;
            }
        }
        return size;
    }
}

위 방법으로도 실행 시간을 초과

이중 for문으로 인하여 성능 저하가 발행 할 것으로 추측

 

형의 롤케익의 토핑을 Set, 동생의 토핑을 Map에 설정

Set의 초기값은 토핑의 첫번째 값을 추가

두번째 값부터 마지막 값까지는 Map에 key는 토핑의 종류, value는 해당 토핑의 개수를 설정

 

동생의 토핑인 Map에서 값을 하나씩 빼면서 형의 토핑인 Set에 추가하고 Set과 Map의 길이를 비교하여 답을 계산

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Q30_132265 {
    public int solution(int[] topping) {
        int length = topping.length;

        Set<Integer> set = new HashSet<>();
        Map<Integer, Integer> map = new HashMap<>();

        set.add(topping[0]);
        for (int i = 1; i < length; i++) {
            int number = topping[i];
            map.put(number, map.getOrDefault(number, 0) + 1);
        }

        int answer = 0;
        for (int i = 1; i < length; i++) {
            int number = topping[i];

            set.add(number);

            int numberSize = map.get(number);
            if (numberSize == 1) {
                map.remove(number);
            } else {
                map.put(number, numberSize - 1);
            }

            if (set.size() == map.size()) {
                answer++;
            }
        }

        return answer;
    }
}