연습문제 > 덧칠하기

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

프로그래머스

처음에 이런식으로 접근 했다

// n : 6, m : 1, section : [1, 3, 5]
// answer : 3
// 반환 결과 : 5

롤러의 길이 m 이 1일 때는 다른 결과가 나오므로

if (m === 1) {
    return section.length;
}

를 추가했지만

60% 밖에 통과를 못했고

 

// 입력값 〉 5, 2, [1, 2, 5]

// 기댓값 〉 2

// 반환 결과 : 5

라는 반례를 찾아냄

 

결국 롤러의 길이만큼 section 의 배열을 짤라서 칠해지는지 여부를 파악해가면서 돌려야 함

 

이런 식으로 2차원 배열로 추가하게 끔 해서 2차원 배열의 length를 리턴하는 식으로 해결하려고 했는데

이거보다 더 간단하게 푸는 방법이 떠오름 (사실은 엄청난 삽질을 통해...)

 

 

function solution(n, m, section) {
    let arr = [];
    
    for (let i = 0; i < section.length; i++) {
        if (i === 0) arr.push([section[i]]);
        const currentArr = arr[i];
        const lastArr = currentArr[currentArr.length - 1];
        let width = 1;
        let j = i + 1;

        const nextSection = section[j];
        while (width <= m && nextSection !== undefined) {
            width += section[j] - lastArr;
            if (width <= m) currentArr.push(nextSection);
            console.log(width, nextSection, lastArr, currentArr);
        }

        if (nextSection !== undefined) {
            arr.push([nextSection]);
        }
        console.log(arr);

    }

}

 

이런식으로

처음 i === 0 일 때 시작지점에 최초의 2차원 배열 arr[i] 를 추가하면

[ [2] ] 이 되고

여기서 section 의 다음 index인 3, 6을 조건에 맞게 롤러의 길이만큼만 추가하는 식으로

 

롤러의 길이를 width += section[j] - lastArr; 식으로 계산해서 m(롤러 길이)가 넘어가면

다음 2차원 배열이 추가되도록 해보려고 했지만

while 문이 index랑 얽혀서 꼬여버림

 

최종 정답...

function solution(n, m, section) {
    let arr = [];  // 결과를 저장할 2차원 배열
    let i = 0;     // section 배열의 인덱스

    while (i < section.length) {
        let coveredSections = [section[i]]; // 현재 롤러로 시작하는 섹션을 추가
        let lastArr = section[i];           // 마지막으로 칠한 구역을 기록
        let width = 1;                      // 현재 롤러로 칠할 수 있는 너비 초기화
        let j = i + 1;                      // 다음 섹션의 인덱스

        // 다음 섹션들을 검토하면서 롤러의 너비를 넘지 않는 범위 내에서 추가
        while (j < section.length && (section[j] - lastArr + width <= m)) {
            coveredSections.push(section[j]);
            width += section[j] - lastArr;  // 롤러의 현재 너비 업데이트
            lastArr = section[j];           // 마지막으로 칠한 구역 업데이트
            j++;
        }

        // 결과 배열에 현재 롤러로 커버된 섹션들의 배열 추가
        arr.push(coveredSections);
        i = j;  // 다음 롤러의 시작점으로 인덱스 업데이트
    }

    console.log(arr);
    return arr.length;
}

테스트 케이스까지 추가해서

 

통과

for 문 사용할 때 

function solution(n, m, section) {
    let arr = [];  // 결과를 저장할 2차원 배열

    for (let i = 0; i < section.length;) {
        let coveredSections = [section[i]]; // 현재 롤러로 시작하는 섹션을 추가
        let lastArr = section[i];           // 마지막으로 칠한 구역을 기록
        let width = 1;                      // 현재 롤러로 칠할 수 있는 너비 초기화
        let j = i + 1;                      // 다음 섹션의 인덱스

        // 다음 섹션들을 검토하면서 롤러의 너비를 넘지 않는 범위 내에서 추가
        while (j < section.length && (section[j] - lastArr + width <= m)) {
            coveredSections.push(section[j]);
            width += section[j] - lastArr;  // 롤러의 현재 너비 업데이트
            lastArr = section[j];           // 마지막으로 칠한 구역 업데이트
            j++;
        }

        // 결과 배열에 현재 롤러로 커버된 섹션들의 배열 추가
        arr.push(coveredSections);
        i = j;  // 다음 롤러의 시작점으로 인덱스 업데이트
    }

    console.log(arr);
    return arr.length;
}