[프로그래머스] 롤케이크 자르기 - LV2

📝 문제

 

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

프로그래머스

[설명]

케이크를 1번 잘라서 토핑의 개수가 같아지는 개수 구하기

 

[접근 방법]

topping 배열에서 중복되는 토핑이 있으므로 중복을 제거해주는 hashset을 활용해 구현

배열 2개를 만들어 하나의 배열은 앞에서부터 탐색, 또다른 배열은 뒤에서부터 탐색 후

대각선 비교를 해서 토핑의 개수가 같은 경우를 롤케이크를 공평하게 자르는 수(answer)에 포함하기

하나의 롤케이크를 잘라서 비교를 하기 때문에 하나의 HashSet를 이용

-> 중간에 HashSet을 한 번 비워줘야한다. (set.clear() : 모든 값 제거)

 

[주의 사항]

- 이중 반복문을 돌면, 시간 초과 발생

- 단일 for문으로 구현해 시간 복잡도 O(N)으로 해결!

- HashSet 사용법 잘 기억하자.

- 무조건 손으로 써가면서 해결법 찾아보자.

🔑 풀이

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(); // set 비우기

            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;
        }
    }

 

 

 

📌 [TIL]

HashSet 활용법

 

 

⭐️ 공부 참고 자료

---

https://coding-factory.tistory.com/554

[Java] 자바 HashSet 사용법 & 예제 총정리