Unity 내일배움캠프 TIL 1010 | 프로그래머스 롤케이크 자르기

롤케이크 자르기

문제

케이크 토핑 배열이 주어질 때, 철수와 동생이 케이크 토핑의 종류를 동일하게 나눠가질 수 있는 경우의 수를 구하는 문제

제한 사항

1 <= topping의 길이 <= 1,000,000
1 <= topping의 원소 <= 10,000

입출력 예

topping	result
[1, 2, 1, 3, 1, 4, 1, 2]	2
[1, 2, 3, 1, 4]	0

생각의 흐름

• topping 배열의 길이가 매우 길기 때문에 이중 for문 같은 방식은 시간 초과가 날 것이다
  -> topping 배열을 한 번 순회하면서 계산할 수 있어야 함
• 형에게는 첫 번째 토핑만, 동생에게는 두 번째 토핑~마지막 토핑까지의 조각을 처음에 주고 시작
• 형의 토핑을 하나씩 늘려가면서 종류를 세고, 동생의 토핑을 하나씩 줄여가면서 토핑의 종류를 센다
  -> 이 때 토핑 종류가 같아지면 answer를 증가
• 동생의 토핑을 저장할 때, 토핑의 종류와 개수를 함께 저장해야 한다
  -> Dictionary 사용

풀이

• 처음에는 형과 동생의 토핑을 모두 Dictionary에 담아 저장했는데, 형의 경우는 토핑의 종류를 추가하는 연산만 하기 때문에 토핑의 종류만 구분할 수 있으면 되었다.
  그래서 사용한 것이 HashSet

using System;
using System.Collections.Generic;

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

        HashSet<int> firstTopping = new HashSet<int>();
        Dictionary<int, int> secondTopping = new Dictionary<int, int>();

        firstTopping.Add(topping[0]);
        for (int i = 1; i < topping.Length; i++)
        {
            if (secondTopping.ContainsKey(topping[i])) secondTopping[topping[i]]++;
            else secondTopping.Add(topping[i], 1);
        }

        if (firstTopping.Count == secondTopping.Count) answer++;

        for (int i = 1; i < topping.Length - 1; i++)
        {
            int curTopping = topping[i];
            firstTopping.Add(curTopping);
            if ((secondTopping[curTopping] - 1) == 0) secondTopping.Remove(curTopping);
            else secondTopping[curTopping]--;
        
            if (firstTopping.Count == secondTopping.Count) answer++;
        }

        return answer;
    }
}

1. HashSet(형의 토핑), Dictionary(동생의 토핑)을 선언
2. 형의 토핑에 첫 번째 토핑 추가
   동생의 토핑에 두 번째 토핑부터 마지막 토핑까지 추가
   이 때, 토핑이 이미 존재한다면 개수를 늘리고 새로운 토핑이라면 추가
3. 형의 토핑이 1개이고, 동생의 토핑이 topping.Length - 1인 경우를 계산하기 위해 형의 토핑 종류와 동생의 토핑 종류 개수를 비교
   -> 사실 2~3의 과정은 그냥 4번에서 한꺼번에 처리해도 될 것 같다
   근데 수정하지 않고 이대로 남겨둔 이유는 재밌는 사실을 발견했기 때문!
   아래에서 설명할 예정 ~.~
4. topping 배열을 순회하면서 현재 토핑에 대하여 연산
   • 형의 토핑 추가
   • 동생의 토핑에서 현재 토핑을 제거
     이 때, 남은 토핑 개수가 1개라면 동생의 토핑 Dictionary에서 해당 토핑을 삭제
5. 형의 토핑 종류와 동생의 토핑 종류 개수가 같다면 answer를 증가

HashSet과 Dictionary 풀이 비교

• HashSet
  • 풀이 코드대로 풀었을 경우
    
  • for문에서 형의 토핑을 추가할 때 아래 조건을 추가하였을 경우

    if (!firstTopping.Contains(curTopping)) firstTopping.Add(curTopping);

    

• Dictionary
  

• 문제를 풀 때는 Dictionary보다 HashSet이 더 빠른 실행 속도를 가졌는데, 다시 해보니 크게 차이 나지는 않는 것 같다.
  오히려 Dictionary가 더 빠른 경우도 있고..!

여담

• 풀이에서 3번 과정을 생략해도 테스트 케이스는 통과를 한다는 재밌는 사실

• 하지만 "질문하기"에 올라온 반례 테스트 케이스들은 통과하지 못한다.

이제 개인 프로젝트 야근하러...
20000...

끗!