[PCCP] Lv2: 롤케이크 자르기(132265) 해설

문제

- 문제 링크: 롤케이크 자르기

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: topping의 길이

- topping의 길이만큼 반복문을 수행: O(N)

- 내부 연산들은 모두 O(1)

- 최종 시간 복잡도: O(N)

import java.util.HashMap;
import java.util.HashSet;

class Solution {
    public int solution(int[] topping) {
        // 결과값을 저장할 변수 초기화
        int answer = 0;
        
        // 토핑의 개수를 세어서 해시맵에 저장
        HashMap<Integer, Integer> toppingMap = new HashMap<>();
        for (int t : topping) {
            toppingMap.put(t, toppingMap.getOrDefault(t, 0) + 1);
        }
        
        // 토핑의 종류를 저장할 해시셋
        HashSet<Integer> toppingSet = new HashSet<>();
        
        // 롤케이크를 하나씩 해시셋에 넣으면서 확인
        for (int t : topping) {
            // 해시셋에 토핑을 추가하고, 해당 토핑의 전체 개수를 해시맵에서 줄임
            toppingSet.add(t);
            toppingMap.put(t, toppingMap.get(t) - 1);
            
            // 토핑의 전체 개수가 0이면 해시맵에서 제거
            if (toppingMap.get(t) == 0)
                toppingMap.remove(t);
            
            // 토핑의 종류의 수가 같다면
            if (toppingSet.size() == toppingMap.size())
                answer++;
        }
        // 공평하게 나눌 수 있는 방법의 수 반환
        return answer;
    }
}

solution 2) 배열과 해시셋만ㅇ르 이용

- 철수를 기준으로 앞부터 해시셋을 이용하여 토핑의 종류를 세어 arr1 배열에 저장하고 동생 기준으로는 뒤부터 동일하게 해시셋으로 토핑 종류를 세어 arr2 배열에 저장

- 토핑의 종류 수가 저장된 배열에서 arr1[i] == arr2[i + 1]의 개수를 세면 답이 나옴

import java.util.HashSet;

class Solution {
    public int solution(int[] topping) {
        HashSet<Integer> set = new HashSet<>();
        int[] arr1 = new int[topping.length];
        int[] arr2 = new int[topping.length];
        
        for (int i = 0; i < topping.length; ++i) {
            set.add(topping[i]);
            arr1[i] = set.size();
        }
        
        set.clear();
        
        for (int i = topping.length - 1; i >= 0; --i) {
            set.add(topping[i]);
            arr2[i] = set.size();
        }
        
        int answer = 0;
        for (int i = 0; i < topping.length - 1; ++i) {
            if (arr1[i] == arr2[i + 1])
                answer++;
        }
        return answer;
    }
}

solution 3)

#include<>

 

(Python)

solution 1)

- N: topping의 길이

- topping의 길이만큼 반복문을 수행: O(N)

- 내부 연산들은 모두 O(1)

- 최종 시간 복잡도: O(N)

from collections import Counter

def solution(topping):
    # 결과값을 저장할 변수 초기화
    split_count = 0
    
    # 토핑의 개수를 세어서 딕셔너리에 저장
    topping_counter = Counter(topping)
    
    # 절반에 속한 토핑의 종류를 저장할 집합
    half_topping_set = set()
    
    # 롤케이크를 하나씩 절반에 넣으면서 확인
    for t in topping:
        # 절반에 토핑을 추가하고, 해당토핑의 전체 개수를 줄임
        half_topping_set.add(t)
        topping_counter[t] -= 1
        
        # 토핑의 전체 개수가 0이면 딕셔너리에서 제거
        if topping_counter[t] == 0:
            topping_counter.pop(t)
        
        # 토핑의 종류의 수가 같다면
        if len(half_topping_set) == len(topping_counter):
            split_count += 1
            
    # 공평하게 나눌 수 있는 방법의 수 반환
    return split_count

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: topping의 길이

- topping의 길이만큼 반복문을 수행: O(N)

- 내부 연산자들은 모두 O(1)

- 최종 시간 복잡도: O(N)

function solution(topping) {
    // 결괏값을 저장할 변수 초기화
    let splitCount = 0;
    
    // 토핑의 개수를 세어서 Map에 저장
    const toppingCounter = new Map();
    for (const t of topping) {
        toppingCounter.set(t, (toppingCounter.get(t) || 0) + 1);
    }
    
    // 절반에 속한 토핑의 종류를 저장할 set
    const halfToppingSet = new Set();
    
    // 롤케이크를 하나씩 절반에 넣으면서 확인
    for (const t of topping) {
        // 절반에 토핑을 추가하고, 해당 토핑의 전체 개수를 줄임
        halfToppingSet.add(t);
        toppingCounter.set(t, toppingCounter.get(t) - 1);
        
        // 토핑의 전체 개수가 0이면 오브젝트에서 제거
        if (toppingCounter.get(t) === 0) {
            toppingCounter.delete(t);
        }
        
        // 토핑의 종류 수가 같다면
        if (halfToppingSet.size === toppingCounter.size) {
            splitCount += 1;
        }
    }
    
    // 공평하게 나눌 수 있는 방법의 수 반환
    return splitCount;
}

solution 2)

import

solution 3)

import