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

https://school.programmers.co.kr/learn/courses/30/lessons/132265

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

롤케이크를 2개로 자를 수 있는 모든 경우의 수 중에 토핑의 종류가 같은 경우를 구하는 문제

- 자른 2개의 영역 안에 토핑의 종류를 매번 구하기에는 비용소모가 너무 크므로 Dictionary에 담아 같은 토핑의 고유 번호를 키로 가지고 키 값에 따른 토핑의 개수를 값으로 가짐

- 순서는 변하지 않고 이동해야 하기 때문에 Queue를 이용함

https://godgjwnsgur7.tistory.com/46

[C#] 자료구조 ( 제네릭 컬렉션 )

ex) 1 2 3 4 5

-> 1 / 2 3 4 5

-> 1 2 / 3 4 5

-> 1 2 3 / 4 5

-> 1 2 3 4 / 5

 

주석 참조

    using System;
    using System.Collections.Generic;

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

            var dict1 = new Dictionary<int, int>(); // 철수 토핑 개수
            var dict2 = new Dictionary<int, int>(); // 동생 토핑 개수
            var queue = new Queue<int>(); // 동생이 가진 케이크

            // 초기 값 세팅 (철수 1조각, 동생 나머지조각으로 시작)
            dict1.Add(topping[0], 1);
            for (int i = 1; i < topping.Length; i++)
            {
                queue.Enqueue(topping[i]);
                if (!dict2.ContainsKey(topping[i]))
                    dict2.Add(topping[i], 1);
                else
                    dict2[topping[i]]++;
            }

            // 토핑 개수 비교
            if (dict1.Count == dict2.Count)
                answer++;

            // 동생 -> 철수
            while (queue.Count > 1)
            {
                // 동생쪽의 한조각을 넘겨줌
                int num = queue.Dequeue();
                if (dict2[num] <= 1)
                    dict2.Remove(num);
                else
                    dict2[num]--;

                // 동생쪽에서 준 한조각을 철수가 받음
                if (!dict1.ContainsKey(num))
                    dict1.Add(num, 1);
                else
                    dict1[num]++;

                // 토핑 개수 비교
                if (dict1.Count == dict2.Count)
                    answer++;
            }

            return answer;
        }
    }

 

+ 만약 롤케이크가 아닌 케이크를 조각으로 자른다고 생각한다면 queue를 2개 선언해 동생 -> 철수 / 철수 -> 동생으로 로직을 짜면 됨 ( 사실 처음에 이렇게 풀어서 제출했었었음 ㅎ... )

ex) 1 2 3 4 5

-> 1 / 2 3 4 5

-> 1 2 / 3 4 5

-> 1 2 3 / 4 5

-> 1 2 3 4 / 5

-> 2 3 4 / 5 1

-> 3 4 / 5 1 2

-> 4 / 5 1 2 3