[프로그래머스] lv2 롤케이크 자르기(JAVA)

1. 문제

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

프로그래머스

 

---

 

2. 문제 풀이 겸 회고

문제를 읽으면서 로직이 생각나서 바로 구현하였다. 혹시 다르게 효율적으로 구현하셨으면 댓글로 공유 부탁드립니댬.

HashSet으로 해결할 수 있는 문제 

for문 돌면서 Set에 저장하고 저장할 때마다 dp라는 배열에 set.size() 를 넣어준다.

i = 0 부터랑 i = topping.lengt-1 이렇게 두 방향으로 해주기

글로 보면 이해 안 되니깐... 나의 보물 그림판으로 그려봤음

검은색은 topping 배열이고

빨간색은 앞서 말했듯이, 중복 제거된 토핑들을 dp 배열에 넣어준 값이다.

 

이제 값을 구할 건데, 주황 부분은 이제 롤케익을 나눈 부분이다. 그래서 for문 돌면서 값 주황 부분값 비교해 주면서 값이 같으면 answer++ 해준다.

이러면 답 나온다.

 

나는 정말 직관적으로 구한 것 같다.. 다른 사람들 코드 보면 map에 넣으면서 한 번에 답을 구하던데...ㅎㅎ....

시간은 그래도 좀 나온 편 같다 (참고하시길)

 

3. 코드

import java.util.*;
class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        HashSet<Integer> set = new HashSet<>();
        int[] dp1 = new int[topping.length];
        int[] dp2 = new int[topping.length];
        for(int i=0;i<topping.length;i++){
            set.add(topping[i]);
            dp1[i] = set.size();
        }
        set.clear();
        for(int i=topping.length-1;i>=0;i--){
            set.add(topping[i]);
            dp2[i] = set.size();
        }
        
        for(int i=0;i<topping.length-1;i++){
            if(dp1[i] == dp2[i+1]){
                answer++;
            }
        }
        // System.out.println(Arrays.toString(dp1));
        // System.out.println(Arrays.toString(dp2));
        
        return answer;
    }
}

 

피드백은 언제나 환영입니다 :) 🌳