[프로그래머스] 롤케이크 자르기 / 자바(Java)

문제

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

프로그래머스

 

---

해설

롤케이크(입력 배열)을 2개로 나누어 앞, 뒤로 확인하는 문제라 정렬을 쓸 수 없기 때문에 앞에서부터 하나씩 따라가며 공평하게 잘렸는가 여부를 판단하며 진행해야 합니다.

topping의 길이가 1,000,000이기 때문에 O(N^2)의 시간복잡도를 가지게 되면 시간초과가 발생해 더 적은 시간복잡도가 필요합니다.

 

topping의 원소의 범위가 1~1000으로 너무 많지 않아 배열을 사용해 해당 토핑의 개수를 저장합니다. 만약 원소의 범위가 너무 크다면 Map같은 다른 자료구조를 사용해도 무방해 보입니다.

 

기록용 배열 log	log[][0]	log[][1]	log[][i]
log[0][] (잘린 롤케이크 앞쪽 정보)	앞쪽 롤케이크의 토핑 종류수	앞쪽 롤케이크의 1번 토핑 수	앞쪽 롤케이크의 i번 토핑 수
log[1][] (잘린 롤케이크 뒤쪽 정보)	뒤쪽 롤케이크의 토핑 종류수	뒤쪽 롤케이크의 1번 토핑 수	뒤쪽 롤케이크의 i번 토핑 수

 

사용할 배열 log에 대한 정보입니다. topping의 원소범위가 1부터 이기 때문에 사용하지 않을 0번 인덱스에 총 토핑 종류수 값을 넣어줍니다.

 

우선 자르지 않은 상태의 롤케이크 정보를 얻기 위해 topping배열을 따라가며 log[0][]배열에 정보를 추가해 줍니다.

이후 topping배열을 다시 따라가며 한 토핑씩 뒤쪽 정보로 변경하며 log[][i]의 값이 0 또는 1이 될 때마다 log[][0]의 값을 변경해주어 롤케이크를 자르는 경우마다 앞, 뒤의 토핑의 종류수를 얻을 수 있습니다.

O(2N)의 시간복잡도로 문제를 해결할 수 있습니다.

 

주의점

• topping의 길이는 최대 1,000,000
• topping의 원소의 범위는 1에서 1,000

---

코드

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        int[][] log  = new int[2][10001];

        for(int cur : topping){
            if(log[0][cur]==0) log[0][0]++;
            log[0][cur]++;
        }
        
        for(int cur : topping){
            log[0][cur]--;
            if(log[0][cur]==0) log[0][0]--;
            if(log[1][cur]==0) log[1][0]++;
            log[1][cur]++;
            if(log[0][0] == log[1][0]) answer++;
        }
        return answer;
    }
}