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

leehyunjon·2022년 11월 2일

Algorithm

목록 보기

119/162

롤케이크 자르기 : https://school.programmers.co.kr/learn/courses/30/lessons/132265

Problem

Solve

topping을 왼쪽과 오른쪽 두 부분으로 나누어 각 부분에 중복을 제외한 토핑의 종류 개수가 동일한 개수를 구하는 문제.
포인터를 기준으로 왼쪽은 추가, 오른쪽은 제거하는 식으로 슬라이딩 윈도우 방식을 사용했습니다.

첫번째 풀이(해결)

왼쪽과 오른쪽의 토핑을 저장할 Map<Integer, Integer>를 선언해줍니다.
그리고 topping배열에서 두 부분으로 나누어 줄 포인터를 하나 지정해주고 포인터를 오른쪽으로 이동시켜주면서 왼쪽은 포인터의 토핑을 추가 또는 증가시켜주고, 오른쪽은 포인터의 토핑을 제거 또는 감소시켜주는 과정을 반복합니다.

		for(int i=point;i<topping.length;i++){
			int t = topping[i];
			//왼쪽 추가 또는 증가
			left.put(t, left.getOrDefault(t, 0)+1);

			//오른쪽 감소
			right.put(t, right.get(t)-1);
            //만약 오른쪽에서 해당 토핑의 개수가 0이라면 map에서 삭제시켜준다.
			if(right.get(t)==0) right.remove(t);

			if(left.size() == right.size()) answer++;
		}

두번째 풀이(개선)

O(N)으로 시간복잡도는 조건에 맞게 잘 해결해주지만, 해결되는 시간이 조금 오래걸려 더 좋은 방법이 없을까 생각하다가 굳이 Map을 사용해야하나라는 생각이 들어 배열을 사용하여 접근은 동일하게 하여 구현하였습니다.

기존 포인터를 사용하지 않고 오른쪽 배열에 모든 토핑의 개수를 초기화 해줍니다. 그리고 토핑 종류의 개수도 초기화 해줍니다.

그리고 topping을 순차적으로 돌면서 해당 토핑을 왼쪽 배열에는 추가해주고, 오른쪽 배열에서는 제거하는 식으로 구현하였습니다.

		//right배열은 모든 토핑의 개수로 초기화되어있는 상태
		for(int t : topping){
        	//해당 토핑 감소
			right[t]--;
            //토핑의 개수가 0이라면 right배열이 가지는 토핑 종류의 개수를 감소
			if(right[t]==0) rightCount--;

			//left배열이 가지고 있지 않은 토핑이 들어온다면 토핑 종류의 개수를 증가
			if(left[t]==0) leftCount++;
            //해당 토핑 개수 증가
			left[t]++;

			//해당 토핑으로 left,right 배열 정보를 갱신시키고 각 토핑 종류의 개수가 동일하다면 answer 증가
			if(leftCount == rightCount) answer++;
		}

Code

import java.util.Map;
import java.util.HashMap;
class Solution {
    public int solution(int[] topping) {
        int[] left = new int[10001];
        int[] right = new int[10001];
        int leftCount = 0;
        int rightCount = 0;
        
        for(int t : topping){
            if(right[t]==0) rightCount++;
            right[t]++;
        }
        
        int answer = 0;
        for(int t : topping){
            right[t]--;
            if(right[t]==0) rightCount--;
            
            if(left[t]==0) leftCount++;
            left[t]++;
            
            if(leftCount == rightCount) answer++;
        }
        
        return answer;
    }
}