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

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

문제풀이

import java.util.*;
class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        
        // 철수가 가지고 있는 토핑 : 조각 수 Map
        Map<Integer, Integer> map_1 = new HashMap<>();
        // 동생이 가지고 있는 토핑 : 조각 수 Map
        Map<Integer, Integer> map_2 = new HashMap<>();
        
        // 1. 동생에게 몰아주기
        for (int e : topping) {
            map_2.put(e, map_2.getOrDefault(e, 0) + 1);
        }
        
        for (int e : topping) {
            // 2.동생이 철수에게 하나씩 주면서 동등하게 나눴는지 비교
            // 하나 줌(증가)
            map_1.put(e, map_1.getOrDefault(e, 0) + 1);
            // 동생이 가진 해당 토핑 조각 개수 조정
            int broRollCount = map_2.get(e);
            map_2.put(e, --broRollCount);
            // 철수에게 주고 나서 토핑 조각이 0개가 됐다면 롤케이크 조각 없음 
            // -> 맵에서 제거
            if(broRollCount == 0) {
                map_2.remove(e);
            }
            
            // 3. 철수와 동생의 가진 토핑 개수를 비교하여 같으면 정답
            // 같은 갯수의 토핑을 가지고 있다면 동등하게 나눈 것
            if(map_1.size() == map_2.size()) {
                answer++;
            }
        }
        return answer;
    }
}

• Map : 토핑 번호 - 조각 수로, 토핑을 잘 나누었는지 검사하기 위해서는 토핑의 수를 검사하면 된다.

  • Map의 size() 메서드 : Key-Value 쌍의 개수 반환
  • ex) 철수의 토핑 Key [1, 2] / 동생의 토핑 키 [2, 3] => size는 둘 다 2로 동일 하여 잘 나눈 것으로 확인

• 동생에게 케이크를 다 준다.

• 동생이 철수에게 케이크를 앞에서부터 하나씩 주면서 동생이 가진 케이크 개수를 갱신하고, 동등하게 잘 나눈 것인지 비교한다.

  • 동생이 나눠주고 나서 개수가 0개라면 Map에서 제거해 준다.

• 동등하게 잘 나눈 것이라면 answer를 +1 해준다.

• 문제 예시 실행 순서 그림
  

정리

• 문제에서 배열의 길이가 100만까지라 했다.

• 제일 간단한 풀이 방식은 아무래도 for 문을 돌면서, 해당 인덱스와 나머지 전체 인덱스로 나누고 다 돌면서 토핑을 Set으로 저장해 Set의 수가 동일한지 확인하면 될 것 같다고 생각했다.

  • ex) for 문 인덱스 1 -> [0, 1] 과 나머지 배열 -> 각각 Set에 토핑 저장 -> 비교

• 하지만 위 방식으로 할 경우 2중 for 문으로 O(N^2) => 100만 * 100만 => 최악은 1조번의 연산을 해야한다.

• 프로그래머스 등 1초 이내에 문제를 해결해야 하기에, 최대 시간 복잡도를 1억 이하로 조정해야 하기에 O(N) + O(N) = O(2N) => 2백만번으로 해결했다.

  • 출처 - Big O notation 과 시간 제한 (보통 1초 제한이라고 하면 어느정도?)

• 풀이 출처 : [JAVA] LV2. 롤케이크 자르기