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

---

프로그래머스 Lv2 - 롤케이크 자르기 문제

프로그래머스 레벨 2 롤케이크 자르기 문제를 풀이했다.

처음 풀이때는 어? 너무 쉽잖아.. set을 사용해서 특정 길이만큼 배열을 잘라가면서 사이즈 비교하면 되겠다! 하고 구현을 해보았지만.. 문제 조건의 topping의 크기도 100만이였고, 이중 반복문을 사용하니 시간복잡도가 높아지고.. 결국에는 효율성 테스트도 못 가보고 기본 테스트 케이스에서도 실패를 해버렸따...

Set을 사용했던 실패 코드..

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        for(int i = 1; i < topping.length; i++) {
            Set<Integer> bigBro = new HashSet<>();
            Set<Integer> bro = new HashSet<>();
            for(int j = 0; j < topping.length; j++) {
                if(j < i) {
                    bigBro.add(topping[j]);
                } else {
                    bro.add(topping[j]);
                }
            }
            if(bigBro.size() == bro.size()) {
                answer++;
            }
        }
        return answer;
    }
}

실패를하고, 해싱을 통해 해결해보자! 하여 로직 느낌은 비슷하지만 훨씬 더 효율성 좋게 코드를 변경했다.
단순하게 표현한 로직 흐름은 아래와 같다.

1. 형에게 모든 토핑을 몰아주기
2. 동생이 하나씩 뻇어가며 둘의 크기 비교
3. 둘이 동일하면 정답에 +1
4. 정답 리턴

이렇게 변경하니 이중 반복문도 없어지고 시간복잡도도 훨씬 줄어들었다.
두 번째 반복문을 bigBro를 기준으로 순회하는것이 아닌 topping 기준으로 순회하는 이유는
컬렉션 객체에서 반복을 하는 도중 내부 요소를 삭제할 경우 ConcurrentModificationException이 발생할 수 있다는 것을 알고 있었고, 따라서 조금 불편하고 효율성이 떨어지더라도 topping을 기준으로 반복문을 순회하였다.
문제 풀이 후 다른 방법을 구글링해보니

1. Iterator 객체를 사용하여 순회하면서 요소 삭제는 안전하다.
2. removeIf() 메소드 사용

등의 방법들도 존재했다. 나중에 적용해봐야겠다~~

CutRollCake.java

package com.example.Programmers.Lv2;

import java.util.HashMap;
import java.util.Map;

/**
 * 프로그래머스 Lv2 - 롤케이크 자르기 문제
 */
public class CutRollCake {
    public int solution(int[] topping) {
        int answer = 0;
        // 형, 동생 맵 선언
        Map<Integer, Integer> bigBro = new HashMap<>();
        Map<Integer, Integer> bro = new HashMap<>();

        // 형에게 모든 종류의 토핑을 추가(초기화)
        for (int i = 0; i < topping.length; i++) {
            if (bigBro.containsKey(topping[i])) {
                bigBro.replace(topping[i], bigBro.get(topping[i]) + 1);
            } else {
                bigBro.put(topping[i], 1);
            }
        }

        /**
         * 반복을 통하여 동생에게 토핑 추가, 형에게는 토핑 제거
         * 그 후 형, 동생의 토핑 개수를 비교하여 둘 다 동일하다면 정답 1증가
         */
        for (int i = 0; i < topping.length; i++) {
            // 동생에게 토핑 추가(토핑이 이미 있다면 개수 +1, 없다면 토핑 추가)
            if (bro.containsKey(topping[i])) {
                bro.replace(topping[i], bro.get(topping[i]) + 1);
            } else {
                bro.put(topping[i], 1);
            }

            // 형에게 토핑 제거(이미 한 개 이상있는 토핑이면 개수 -1, 없다면 토핑 삭제)
            if (bigBro.get(topping[i]) != 1) {
                bigBro.replace(topping[i], bigBro.get(topping[i]) - 1);
            } else {
                bigBro.remove(topping[i]);
            }

            // 둘의 토핑 종류 비교
            if (bigBro.size() == bro.size()) {
                answer++;
            }
        }

        return answer;
    }
}

CutRollCakeTest.java

package com.example.Programmers.Lv2;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class CutRollCakeTest {
    @Test
    public void testCutRollCake() {
        CutRollCake c = new CutRollCake();

        int result1 = c.solution(new int[] { 1, 2, 1, 3, 1, 4, 1, 2 });
        int result2 = c.solution(new int[] { 1, 2, 3, 1, 4 });

        assertEquals(2, result1);
        assertEquals(0, result2);
    }
}