(알고리즘 스터디) 12주차 월_(Programmers) 롤케이크 자르기

🌟 프로그래머스 / 연습문제 / Level 2 / 롤케이크 자르기

📃 문제

프로그래머스

🚫 제한 사항

• 1 ≤ topping의 길이 ≤ 1,000,000
  • 1 ≤ topping의 원소 ≤ 10,000

👀 입출력 예

topping	result
[1, 2, 1, 3, 1, 4, 1, 2]	2
[1, 2, 3, 1, 4]	0

🤔 풀이 방법

1️⃣ 배열

① 기본 아이디어

(1) 배열 생성

➡️ 주어진 topping 배열을 좌에서 우로 한 번 & 우에서 좌로 한 번 탐색하며, 토핑의 종류의 개수를 기록한 배열을 만든다.

ex) 입출력 예 1 의 경우 : [1, 2, 1, 3, 1, 4, 1, 2]
① 좌 ➡️ 우 [1, 2, 2, 3, 3, 4, 4, 4]
② 우 ➡️ 좌 [4, 4, 4, 4, 3, 3, 2, 1]

➡️ 이 때, 각 방향마다 이미 있는 토핑인지 확인하는 배열과 토핑 종류의 개수를 저장하는 배열이 필요하다. (총 4개의 배열 생성)

// boolean 배열 생성 (토핑 존재 확인)
boolean[] ltrCheck = new boolean[max];
boolean[] rtlCheck = new boolean[max];
// int 배열 생성 (토핑 종류의 개수 저장)
int[] ltrCnt = new int[len];
int[] rtlCnt = new int[len];

(2) ltrCnt 와 rtlCnt 배열을 채우는 과정

➡️ Check 배열을 통해 이전에 있었던 토핑인지를 확인한다.

ex) 입출력 예 1 의 경우 : [1, 2, 1, 3, 1, 4, 1, 2] (좌 ➡️ 우 탐색)
① index = 0 : 토핑 1
➡️ (초기화) 첫번째 토핑은 무조건 처음이기 때문에 ltrCnt 도 1이 되고 동시에 토핑 1 도 true 가 된다.
ltrCheck [true, false, false, false] / ltrCnt [1, 0, 0, 0, 0, 0, 0, 0]
② index = 1 : 토핑 2
➡️ 토핑 2 의 경우 ltrCheck 를 확인해보면 false 로 새로운 토핑이다. 따라서 ltrCnt 도 +1 이 되면서 토핑 2 는 true 로 바꿔준다.
ltrCheck [true, true, false, false] / ltrCnt [1, 2, 0, 0, 0, 0, 0, 0]
③ index = 3 : 토핑 1
➡️ ltrCheck 를 확인해보면 토핑 1 은 이미 존재했던 토핑이다. 따라서 ltrCnt 과 ltrCheck 에는 변화가 없다.
ltrCheck [true, true, false, false] / ltrCnt [1, 2, 2, 0, 0, 0, 0, 0]
(해당 과정을 끝까지 반복)

// 좌 ➡️ 우 탐색
for (int i=1; i<len; i++) {
    tmp = topping[i];

    if (ltrCheck[tmp-1]) { // 토핑이 존재하는 경우
        ltrCnt[i] = ltrCnt[i-1];
        continue;
    }
    // 새로운 토핑인 경우
    ltrCheck[tmp-1] = true;
    ltrCnt[i] = ltrCnt[i-1]+1;
}

(3) 케이크 자르기

➡️ 예시 1을 위처럼 실행하면 아래와 같이 된다.

① 좌 ➡️ 우 [1, 2, 2, 3, 3, 4, 4, 4]
② 우 ➡️ 좌 [4, 4, 4, 4, 3, 3, 2, 1]

➡️ 이때 양쪽에서 좁혔을 때 만나는 지점에서 종류의 개수가 같으면 공평한 나누기가 된다.

// 케이크 자르기
for (int i=0; i<len-1; i++) {
    if (ltrCnt[i] == rtlCnt[i+1]) {
        answer++;
    }
}

② 결과

➡️ 반복문을 자주 돌며 탐색하다보니, 배열이 길어질수록 시간도 증가한다. 그래도 이중으로는 돌지 않기 때문에 복잡도는 O(n) 이다.

💻 풀이 코드

class Solution {
    public int solution(int[] topping) {
        int answer = 0;
        int len = topping.length;
        
        int max = 0;
        for (int i=0; i<len; i++) {
            if (max < topping[i]) {
                max = topping[i];
            }
        }
        
        // boolean 배열 생성
        boolean[] ltrCheck = new boolean[max];
        boolean[] rtlCheck = new boolean[max];
        // int 배열 생성
        int[] ltrCnt = new int[len];
        int[] rtlCnt = new int[len];
        
        // 초기화
        ltrCnt[0] = 1;
        ltrCheck[topping[0]-1] = true;
        
        rtlCnt[len-1] = 1;
        rtlCheck[topping[len-1]-1] = true;
        
        int tmp = 0;
        
        // 좌 ➡️ 우 탐색
        for (int i=1; i<len; i++) {
            tmp = topping[i];
            
            if (ltrCheck[tmp-1]) {
                ltrCnt[i] = ltrCnt[i-1];
                continue;
            }
            ltrCheck[tmp-1] = true;
            ltrCnt[i] = ltrCnt[i-1]+1;
        }
        // 우 ➡️ 좌 탐색
        for (int i=len-2; i>-1; i--) {
            tmp = topping[i];
            
            if (rtlCheck[tmp-1]) {
                rtlCnt[i] = rtlCnt[i+1];
                continue;
            }
            rtlCheck[tmp-1] = true;
            rtlCnt[i] = rtlCnt[i+1]+1;
        }
        
        // 케이크 자르기
        for (int i=0; i<len-1; i++) {
            if (ltrCnt[i] == rtlCnt[i+1]) {
                answer++;
            }
        }
        
        return answer;
    }
}

 

[unrated] Title: 롤케이크 자르기, Time: 25.88 ms, Memory: 145 MB -BaekjoonHub · Young998904/Practice_Algorithm_Auto@03b2