[프로그래머스] 롤케이크 자르기 풀이 / JavaScript

프로그래머스

 

작성 코드 (1차 시도 / 통과)

function solution(topping) {
    let result = 0
    let [lCnt, rCnt] = [1, 0]
    let [lArr, rArr] = [Array(topping.length).fill(0), Array(topping.length).fill(0)]
	// 초기 값 세팅
	lArr[topping[0]] += 1
    for (let i = 1; i < topping.length; i += 1) {
        if (!rArr[topping[i]]) rCnt += 1
        rArr[topping[i]] += 1
    }
    // N번 순회
    for (let i = 1; i < topping.length; i += 1) {
        if (!lArr[topping[i]]) {
            lArr[topping[i]] += 1
            lCnt += 1
        }
        if (!(rArr[topping[i]] -= 1)) rCnt -= 1
        if (lCnt === rCnt) result += 1
    }
    return result
}

 

구현 로직

토핑 배열의 최대 길이가 1,000,000 이므로 O(N)이내의 복잡도로 알고리즘을 짜야 합니다.

 

1. 왼쪽과 오른쪽 배열을 만들어 초기 값 세팅.

- 초기 세팅은 index 1을 기준으로 분할합니다. [1, 1, 1, 1, 1 .. ] 와 같은 케이스가 있을 수 있기 때문입니다.

- 각 배열의 index의미는 topping 원소의 개수를 의미합니다. 예를 들어 index 5 자리에는 5번 토핑이 몇개 들어있는지를 표시합니다.

- 초기값으로 왼쪽 배열에는 topping의 첫번째 원소만, 오른쪽 배열에는 index1부터 끝까지 순회하며 토핑의 개수를 카운트합니다. 또한 왼쪽 배열와 오른쪽 배열에서 중복되지 않는 토핑의 개수를 의미하는 lCnt, rCnt의 초기 값도 카운트합니다. 나중에 이 두 값을 비교해 동일한 경우는 문제에서 요구하는 공평한 경우를 의미합니다.

- 테스트 케이스1의 경우 왼쪽 배열과 오른쪽 배열의 초기 값은 다음과 같이 구성됩니다. [ 0, 1, 0, 0, 0, 0, 0, 0 ] [ 0, 3, 2, 1, 1, 0, 0, 0 ]

- 테스트 케이스1의 경우 lCnt는 1, rCnt 4의 초기 값을 가집니다.

 

2. index 1부터 한자리씩 이동해가며 공평한 경우를 확인.

- 오른쪽 배열에서 토핑 하나를 왼쪽 배열로 옮깁니다. (index를 1씩 증가시키는 것을 의미합니다)

- 만약 옮긴 토핑이 왼쪽 배열에서 없는 토핑이라면 추가해줍니다.

- 왼쪽 배열로 하나를 옮겼으므로 오른쪽 배열에서는 옮긴 값을 제거해야 합니다. 만약 옮겼는데 옮긴 값의 개수가 0이 되어버리면 rCnt를 1 감소시킵니다.

- 테스트 케이스1의 경우 i가 1일 때 왼쪽 배열과 오른쪽 배열은 다음과 같습니다. [ 0, 1, 1, 0, 0, 0, 0, 0 ] [ 0, 3, 1, 1, 1, 0, 0, 0 ] 

- 테스트 케이스1의 경우 i가 2일 때 왼쪽 배열과 오른쪽 배열은 다음과 같습니다. [ 0, 1, 1, 0, 0, 0, 0, 0 ] [ 0, 2, 1, 1, 1, 0, 0, 0 ]

- 테스트 케이스1의 경우 i가 3일 때 왼쪽 배열과 오른쪽 배열은 다음과 같습니다. [ 0, 1, 1, 1, 0, 0, 0, 0 ] [ 0, 2, 1, 0, 1, 0, 0, 0 ]. 이때 lCnt와 rCnt가 3개씩으로 동일하므로 결괏값을 1 증가시킵니다.

- 이 과정을 반복하면 i가 4일 때도 결괏값이 증가하여 총 결괏값은 2가 됩니다.