C# 롤케이크 자르기 - HashSet / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/132265

 

 

1차시도

public int solution(int[] topping) 
{
    int answer = 0;

    var stack = new Stack<int>(topping);
    var rightSet = new HashSet<int>();

    while(stack.Count > 1)
    {
        int pop = stack.Pop();
        rightSet.Add(pop);

        if(stack.Distinct().Count() == rightSet.Count)
            ++answer;
    }

    return answer;
}

모든 원소를 stack에 담아두고 하나씩 꺼내가면서 hashSet에 넣어서 중복제거하고 갯수확인. 

시간초과.

역시 문제가 너무 쉬운경우 최적화 문제인 듯하다.

 

나의 풀이

public int solution(int[] topping) 
{
    int answer = 0;

    var stack = new Stack<int>(topping);
    var leftDict = topping.GroupBy(g => g)
                          .ToDictionary(g => g.Key, g => g.Count());
    var rightSet = new HashSet<int>();

    while(stack.Count > 1)
    {
        int pop = stack.Pop();
        rightSet.Add(pop);

        if(leftDict[pop] == 1)
            leftDict.Remove(pop);
        else
            leftDict[pop]--;

        if(leftDict.Count == rightSet.Count)
            ++answer;
    }

    return answer;
}

topping 배열의 길이가 엄청 큰 경우

Linq의 Distinct를 사용하거나 hashSet에 하나씩 넣는 방법으로는 연산이 너무 많이 일어난다.

 

결론적으로 한 칸씩 이동할 때마다 조금의 수정을 가하면

왼쪽에 남아있는 토핑의 갯수가 적은 연산으로 바로 구할 수 있는 방법이 필요한 것.