코딩테스트 연습 > 롤케이크 자르기

 

 

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

프로그래머스

 

풀이 - 나의 생각

 

Set을 통해 주어진 Topping의 가짓수를 세면 편합니다.

 

위의 그림처럼

 

왼쪽, 오른쪽 각각의 방향에서 가짓수를 체크합니다.

 

그 후에 롤케이크를 잘랐을 때 가짓수가 같은 경우를 세면 정답을 알 수 있습니다.

 

주의할 점은

 

왼쪽의 인덱스가 2일 경우는 0 ~ 2까지의 토핑 가짓수입니다.

 

오른쪽의 인덱스가 2일 경우 2 ~ n까지의 토핑 가짓수입니다.

 

그렇기때문에 두 경우를 비교하기 위해서는

 

first[i] == second[i+1] 로 비교 해야 합니다.

 

왼쪽 2, 오른쪽 4이므로 공평하지 못함

 

왼쪽 3, 오른쪽 3이므로 공평함

 

 

코드

 

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        /*
        각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 롤케이크가 나누어진 것임
        */
        int answer = 0;
        int len = topping.length;
        int[] first = new int[len], second = new int[len];
        Set<Integer> fNums = new TreeSet<>();
        Set<Integer> sNums = new TreeSet<>();
        for(int i = 0; i < len; i++){
            fNums.add(topping[i]);
            first[i] = fNums.size();
            
            sNums.add(topping[len-i-1]);
            second[len-i-1] = sNums.size();
        }
        for(int i = 0; i < len-1; i++){
            if(first[i] == second[i+1]) answer++;
        }
        return answer;
    }
}

 

 

 

 

 

 

 

다음에 또 봐요