Pre-Onboarding 자바스크립트

혼자 공부하는 자바스크립트 - 3일차

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

챕터 4 - 반복문

새로 배운 것

• 파괴적 처리 / 비파괴적 처리
  실행 후 원래의 자료에 변형이 일어나는 것이 파괴적 처리
  변형이 없는 것이 비파괴적 처리
  초반에는 메모리를 아끼기 위해 새로 변수를 할당하지 않고 원래의 값을 바꾸는 파괴적 처리를 사용하는 경우가 많았지만, 자료의 원본 보존이 이루어지지 않고 최근에는 메모리에 대한 제약이 많이 사라져 비파괴적 처리를 권장함

오늘 고민한 것

• 프로그래머스 문제 : 롤케이크 자르기
  https://school.programmers.co.kr/learn/courses/30/lessons/132265
  문제를 해결하기 위한 코드를 작성하는 것 자체가 어려운 것 보다는, 주어지는 배열의 길이가 1백만까지라 시간초과를 신경써야 했다.
  시간초과를 피하기 위해 반복문은 절대 중첩하지 않는 범위에서 아이디어를 내었다.

-- 1차
left 배열은 비워놓고, count 배열은 includes 함수를 통해 topping[i]가 있는지 확인한다. 만약 이미 있다면 넘어가고, 없는 경우에 push를 통해 topping[i]를 추가하였다. 이후 count 길이를 확인하는 것으로 오른쪽 조각의 토핑 개수를 right에 저장하는 것으로 사전 준비를 마쳤다.

topping 인덱스를 돌면서 includes를 통해 left에 이번 요소가 있는지 확인, 없는 경우 push를 통해 추가하였다. includes를 통해 이번 인덱스의 +1번 인덱스부터 배열의 끝 사이에 이번에 left로 넘어간 토핑이 right에 남아있는지 확인하고, 없는 경우 right--를 수행하여 오른쪽 조각의 토핑 종류를 하나 줄였다. 이후 left의 길이와 right를 비교하여 토핑의 수가 같은지를 확인한다.

결과적으로 정답을 산출하지만, 20개의 케이스 중 6개의 케이스에서 타임오버로 채점되었다. topping의 길이가 아주 긴 경우, 오른쪽 조각에 이번에 왼쪽으로 넘어간 토핑과 같은 토핑이 있는지 확인하는 작업이 문제가 되는 것이라고 판단했다.

-- 2차
사전 작업의 방식을 바꿨다. 여전히 left는 비워놓고 시작한다. count의 경우, 배열에서 객체로 자료형을 변경하였다.
각 자료형의 key는 토핑의 번호, value는 토핑의 개수로 설정했다. topping의 길이만큼 돌며 'key in object'를 사용하여 true를 반환하는 경우 해당 key에 대응하는 value를 하나 증가시키고, false를 반환하는 처음 만나는 key인 경우 value를 1로 설정하여 count에 추가하였다.
이후, count의 키 개수를 배열로 반환하고, 해당 배열의 길이를 right로 설정하여 오른쪽 조각의 토핑 가짓수를 설정하였다.

1차와 마찬가지로, left.includes(topping[i])의 결과를 통해 왼쪽 조각에 토핑을 추가하는 것까지는 동일하게 작업한다.
topping[i]를 key로 갖는 count의 value를 하나 감소시키고, 만약 그 감소한 값이 0인 경우는 오른쪽에 더이상 해당 토핑이 존재하지 않는다고 보았다. 따라서 값이 0인 경우에 right를 하나 감소시킨다.
이후 left의 길이와 right를 비교하여 토핑의 가짓수가 같은지 확인한다.

위와 같이 진행하니 20개의 케이스 모두 시간 내에 정답을 리턴했다.

function solution(topping) {
    var answer = 0;
    
    let count = {}
    for(let i = 0; i < topping.length; i ++) {
        if(topping[i] in count) count[topping[i]]++
        else count[topping[i]] = 1
    }
    let right = Object.keys(count).length
    
    let left = []
    for(let i = 0; i < topping.length-1; i ++){
        if(! left.includes(topping[i])) left.push(topping[i])
        count[topping[i]]--
        
        if(count[topping[i]] == 0) right--
        
        if(left.length == right) answer++
    }
    
    return answer;
}