[Java & Python] 프로그래머스: 롤케이크 자르기

 

https://school.programmers.co.kr/learn/courses/30/lessons/132265?language=python3 

프로그래머스

문제 해설

리스트를 잘라서 중복되지 않는 원소를 세는 식으로 풀 수 있는 문제입니다.

다만 일부 원소를 추출하여 집합형 자료형으로 만드는 과정이 시간 효율성이 떨어지기 때문에 이와 같은 방식으로는 풀 수 없습니다.

Hash를 이용한 자료형을 이용해서 원소를 세서 문제를 해결할 수 있습니다.

Java

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        // 경우의 수 합산
        int answer = 0;
        // Map에 넣기
        HashMap<Integer, Integer> firstCutMap = new HashMap<>();
        HashMap<Integer, Integer> secondCutMap = new HashMap<>();

        // 두 번째 조각에 전부 채우기
        for (int singleTopping : topping) {
            secondCutMap.compute(singleTopping, (k, v) -> v == null ? 1 : v + 1);
        }

        for (int singleTopping : topping) {
            // 첫 번째 조각에 하나씩 채우기
            firstCutMap.compute(singleTopping, (k, v) -> v == null ? 1 : v + 1);
            // 두 번째 조각에서 하나씩 버리기
            secondCutMap.computeIfPresent(singleTopping, (k, v) -> (v <= 1) ? null : v-1);
            // 토핑 개수가 같으면
            if(firstCutMap.keySet().size() == secondCutMap.keySet().size()) {
                answer++;
            }
        }
        return answer;
    }
}

Python

def solution(topping):

    answer = 0
    first_cut: dict = dict()
    second_cut: dict = dict()

    # 두 번재 조각에 토핑 올리기
    for single_topping in topping:
        if second_cut.get(single_topping):
            second_cut[single_topping] += 1
        else:
            second_cut[single_topping] = 1

    # 첫 번째 조각에 토핑 올리고 두 번재 조각에서 빼기
    for single_topping in topping:

        if first_cut.get(single_topping):
            first_cut[single_topping] += 1
        else:
            first_cut[single_topping] = 1

        if second_cut.get(single_topping):
            second_cut[single_topping] -= 1
            if second_cut[single_topping] == 0:
                del(second_cut[single_topping])

        # 토핑 종류 개수가 같으면
        if len(first_cut) == len(second_cut):
            answer += 1

    return answer