[프로그래머스] 롤케이크 자르기 (LV2 - JavaScript)

프로그래머스

1. 문제

제한사항

• 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, 2, 1, 3], [1, 4, 1, 2] 또는 [1, 2, 1, 3, 1], [4, 1, 2]와 같이 자르면 철수와 동생은 각각 세 가지 토핑을 맛볼 수 있습니다. 이 경우 공평하게 롤케이크를 나누는 방법은 위의 두 가지만 존재합니다.

입출력 예 #2

 

롤케이크를 공평하게 나눌 수 없습니다.

 

2. 오답

function solution(topping) {
    let answer = 0;
    
    for (let i=1; i<topping.length; i++) {
        // 토핑이 중복되는 경우가 있기 때문에 Set 객체 사용
        // one: [0 ~ i-1] 인덱스의 토핑
        // two: [i ~ 마지막] 인덱스의 토핑
        const one = new Set(topping.slice(0,i));
        const two = new Set(topping.slice(i));
        
        // 토핑 종류의 수가 같은 경우 answer++
        if (one.size === two.size) answer++;
        // 형의 토핑 종류의 수가 커지는 경우 순회 종료
        if (one.size > two.size) break;
    }
    
    return answer;
}

 

Set 객체와 Array.slice 메서드를 이용해 문제를 간결하고 쉽게 풀었다고 생각했는데 결과는 처참하게 실패...😪😪

반복 실행마다 Set 객체를 생성하고 slice로 배열의 복사본을 생성하기 때문에 시간이 오래 걸리는 것 같다.

3. 정답 풀이

풀이 전략

• Map 객체를 활용

function solution(topping) {
    let answer = 0;
    const older = new Map(); // 형의 토핑
    const younger = new Map(); // 동생의 토핑
    // 형의 토핑을 전체 토핑으로 초기화
    topping.forEach(t => older.set(t, older.get(t) ? older.get(t)+1 : 1));
    
    for(let t of topping) {
    	// 형의 토핑에서 현재 토핑을 1개 제거, 제거 후 0개라면 Map.delete 메서드로 삭제
        older.get(t) > 1 ? older.set(t, older.get(t)-1) : older.delete(t) 
        // 동생의 토핑에 현재 토핑을 1개 추가
        younger.set(t, younger.get(t) ? younger.get(t)+1 : 1);
        
        // 형과 동생의 토핑 종류 수가 같으면 answer++;
        if (older.size === younger.size) answer++;
        // 동생의 토핑 종류 수가 커지면 순회 종료
        if (older.size < younger.size) break;
    }
    
    return answer;
}

 

 

[프로그래머스] 게임 맵 최단 거리 (LV2 - JavaScript)

 

[프로그래머스] 타겟 넘버 (LV2 - JavaScript)