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

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

프로그래머스

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

 

난이도: LEVEL2

알고리즘 유형: 구현

문제 해설

토핑 원소의 범위는 1 ~ 10000이다. 

롤케이크를 잘랐을 때 철수가 가지는 토핑을 기록하는 배열 o1

롤케이크를 잘랐을 때 동생이 가지는 토핑을 기록하는 배열 o2

 

이 2개의 배열을 사용해서 경우의 수를 구한다. 

 

먼저 모든 토핑을 동생이 가지도록 한다. 

이때 중요한 점은 만약 처음 해당 토핑이 기록 즉 if(o2[topping[i]] == 1) 이라면 동생이 가지는 토핑의 종류 수를 늘려준다.

 

이제 다시 topping 배열을 돌면서 1개씩 철수가 가지도록 한다. 

철수도 마찬가지로 if(o1[topping[i]] == 1) 이라면 철수가 가지는 토핑의 종류 수를 늘리고

동생은 o2 해당 index의 토핑을 o2 배열에서 1개 줄인다. 

만약 줄였는데 0이라면 동생은 더 이상 해당 토핑을 가지지 않는 것이니 동생의 종류 수를 하나 줄여준다. 

 

그리고 매번 동생과 철수의 종류 수를 비교해서 같으면 경우의 수에 해당하니 answer 변수를 증가시킨다. 

 

이렇게 풀면 O(2N)에 해결 가능하다. N = topping 배열 길이

 

Map을 사용해서 문제 해결이 가능하지만 

매번 Map size() 체크 / Map 삭제 연산 / Map 추가 연산이 배열을 이용한 풀이보다 더 오래 걸린다. 

 

정답 코드 

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        int [] o1 = new int [10001]; 
        int [] o2 = new int [10001];
        int size = topping.length;
        int o1_cnt = 0; // 토핑 종루 
        int o2_cnt = 0; // 토핑 종류 
        for(int i = 0; i < size; i++){
            o2[topping[i]]++;
            if(o2[topping[i]] == 1) o2_cnt++;
        }
        for(int i = 0; i < size; i++){
            o1[topping[i]]++;
            if(o1[topping[i]] == 1) o1_cnt++;
            o2[topping[i]]--;
            if(o2[topping[i]] == 0) o2_cnt--;
            
            if(o1_cnt == o2_cnt) answer++;
        }
        return answer;
    }
}