99. 롤케이크 자르기

 

기본 틀 :

 

using System;

public class Solution {
    public int solution(int[] topping) {
        int answer = -1;
        return answer;
    }
}

 

문제를 보고 아는 함수들을 조합해서 풀어보았다.

 

topping을 반복문과 Skip().Take() 함수를 활용해 

 

형과 동생의 케이크를 자르고 Distinct() 함수로 중복을 해줬다.

 

그리고, Length를 비교해 개수를 구하고자 시도했다.

 

그 결과...

 

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution {
    public int solution(int[] topping) 
    {
        int count = 0;
        
        for(int i = 0; i < topping.Length; i++)
        {
            int[] oldBrother = topping.Skip(0).Take(i + 1).Distinct().ToArray();
            int[] youngerBrother = topping.Skip(i + 1).Take(topping.Length - i - 1).Distinct().ToArray();
            
            if(oldBrother.Length == youngerBrother.Length) count++;
        }
        
        return count;
    }
}

 

시간복잡도 측면에서 매우 안 좋은 결과가 나왔다...

 

그 이유로는 Skip, Take, Distinct 함수가 각각 O(N)으로 동작하기 때문으로 추측한다.

 

그래서, 시간초과 해결 방법만 찾아 본 결과

 

형이나 동생이 무조건 모든 토핑을 가지고 있게 만든 후

 

차례대로 다른 인원에게 토핑을 주도록 만들면 해결 된다는 글을 보았다.

 

그래서, 

 

Dictionary를 사용해 토핑의 종류를 key로, 개수를 value로 한 사람이 모두 가지도록 지정한 후

 

반복문을 사용해서 다른 사람의 Dictonary에 토핑을 넣어주도록 만들어줬다.

 

이때, 기존에 토핑을 모두 가지고 있던 사람의 해당 포팅 개수가 1개인데 그 1개를 다른 사람에게 줘야 한다면

 

dictionary.Remove()로 가지고 있는 토핑의 종류를 삭제해줬다.

 

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution {
    public int solution(int[] topping) 
    {
        int count = 0;
        Dictionary<int, int> oldBrother = new Dictionary<int, int>();
        Dictionary<int, int> youngerBrother = new Dictionary<int, int>();
        
        
        for(int i = 0; i < topping.Length; i++)
        {
            if(!oldBrother.ContainsKey(topping[i])) oldBrother[topping[i]] = 1;
            else oldBrother[topping[i]]++;
        }
        
        for(int i = 0; i < topping.Length; i++)
        {            
            if(!youngerBrother.ContainsKey(topping[i])) youngerBrother[topping[i]] = 1;
            else youngerBrother[topping[i]]++;
            
            if(oldBrother[topping[i]] > 1) oldBrother[topping[i]] -= 1;
            else if(oldBrother[topping[i]] == 1) oldBrother.Remove(topping[i]);
            
            if(youngerBrother.Count == oldBrother.Count) count++;
        }
        
        return count;
    }
}