[programmers] 롤케이크 자르기

롤케이크 자르기 문제

문제 설명

롤케이크를 2조각으로 자르는데, 각 조각 위에 올라간 토핑의 개수가 같도록 자르는 문제이다. 토핑을 1, 2, 3, 4와 같이 번호로 표시했을 때, 케이크 위의 토핑들이 [1, 2, 1, 3, 1, 4, 1, 2] 순서로 올라가 있게 된다면 [1, 2, 1, 3], [1, 4, 1, 2]의 방법과 [1, 2, 1, 3, 1], [4, 1, 2] 총 2개의 방법으로 토핑이 동일하게 올라가도록 케이크를 자를 수 있다. 공평하게 자르지 못할 경우엔 0을 반환하도록 한다.

제한 사항

• 1 ≤ topping의 길이 ≤ 1,000,000
• 1 ≤ topping의 원소 ≤ 10,000

문제풀이 1.

형과 동생의 토핑을 중복없이 저장하기 위해서 set을 2개를 선언하고, 2중 for문으로 각 set에 index를 한개씩 늘려가면서 토핑을 추가해 주었다. 형의 set에 토핑이 모두 채워질 때 마다 동생과 형의 토핑의 개수를 비교하여 같다면 answer를 1증가시켜 주도록 코드를 짜 보았다.

public int solution(int[] topping) {
    int answer = 0;
    // 공평하게 들어갔는지 확인할 set이 필요하다.
    // topping length 만큼 돌면서 작업을 진행한다.
    Set<Integer> set1 = new HashSet<>();
    Set<Integer> set2 = new HashSet<>();

    for (int i = 0; i < topping.length - 1; i++) {
        set1.add(topping[i]);
        for (int j = i + 1; j < topping.length; j++) {
            set2.add(topping[j]);
            if (set1.size() < set2.size()) {
                break;
            }
        }

        if (set1.size() == set2.size()) {
            answer++;
        }
        set2 = new HashSet<>();
    }
    return answer;
}

결과는 시간초과가 났다. 이중 for문과 한개의 for문이 끝날 때 마다 set을 다시 초기화 시켜주는 과정에서 시간초과가 난 것 같다.

문제풀이 2.

동생의 토핑은 set을 통해 저장하고, 형의 토핑은 map을 이용해 저장하는 방식으로 바꾸었다. map을 이용해 중복된 값은 key로 구분을 하고 몇개가 있는지 확인하고 해당 값을 value에서 차감시키는 방식으로 구현을 했다.

public int solution(int[] topping) {
    int answer = 0;
    // 공평하게 들어갔는지 확인할 set이 필요하다.
    Set<Integer> set = new HashSet<>();
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < topping.length; i++) {
        map.put(topping[i], map.getOrDefault(topping[i], 0) + 1);
    }

    for (int i = 0; i < topping.length; i++) {
        set.add(topping[i]);

        if (map.get(topping[i]) == 1) {
            map.remove(topping[i]);
        } else {
            map.put(topping[i], map.get(topping[i]) - 1);
        }

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

문제풀이2 결과