덧칠하기 [프로그래머스]

문제 설명

 

어느 학교에 페인트가 칠해진 길이가 n미터인 벽이 있습니다. 벽에 동아리, 학회 홍보나 회사 채용 공고 포스터 등을 게시하기 위해 테이프로 붙였다가 철거할 때 떼는 일이 많고 그 과정에서 페인트가 벗겨지곤 합니다. 페인트가 벗겨진 벽이 보기 흉해져 학교는 벽에 페인트를 덧칠하기로 했습니다.

 

넓은 벽 전체에 페인트를 새로 칠하는 대신, 구역을 나누어 일부만 페인트를 새로 칠 함으로써 예산을 아끼려 합니다. 이를 위해 벽을 1미터 길이의 구역 n개로 나누고, 각 구역에 왼쪽부터 순서대로 1번부터 n번까지 번호를 붙였습니다. 그리고 페인트를 칠해야 할 구역들을 정했습니다.

 

벽에 페인트를 칠하는 롤러의 길이는 m미터이고, 롤러로 벽에 페인트를 한 번 칠하는 규칙은 다음과 같습니다.

 

• 롤러가 벽에서 벗어나면 안됩니다.
• 구역의 일부분만 포함되도록 칠하면 안됩니다.

 

즉, 롤러의 좌우측 끝을 구역의 경계선 혹은 벽의 좌우측 끝부분에 맞춘 후 롤러를 위아래로 움직이면서 벽을 칠합니다. 현재 페인트를 칠하는 구역들을 완전히 칠한 후 벽에서 롤러를 떼며, 이를 벽을 한 번 칠했다고 정의합니다.

 

한 구역에 페인트를 여러 번 칠해도 되고 다시 칠해야 할 구역이 아닌 곳에 페인트를 칠해도 되지만 다시 칠하기롤 정한 구역은 적어도 한 번 페인트칠을 해야 합니다. 예산을 아끼기 위해 다시 칠할 구역을 정했듯 마찬가지로 롤러로 페인트칠을 하는 횟수를 최소화하려고 합니다.

 

정수 n,m과 다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열section이 매개변수로 주어질 때 롤러로 페인트칠해야 하는 최소 횟루를 return하는 solution 함수를 작성해 주세요.

 

 

 

제한사항

 

• 1 <= m <= n <= 100,000
• 1 <= section의 길이 <= n
• 1 <= section의 원소 <= n
• section의 원소는 페인트를 다시 칠해야 하는 구역의 번호입니다.
• section에서 같은 원소가 두 번 이상 나타나지 않습니다.
• section의 원소는 오름차순으로 정렬되어 있습니다.

 

입출력 예

 

n	m	section	result
8	4	[2,3,6]	2
5	4	[1,3]	1
4	1	[1,2,3,4]	4

 

 

 

 

 

나의 풀이

 

가장 먼저 든 생각은 페인트가 덧칠되어도 상관없으니 롤러 길이에 따른 페인트 칠 횟수를 페인트가 칠해지는 첫 칸과 끝 칸의 차이에서 롤러의 길이로 나누어주면 페인트칠 횟수가 나올 것이라 생각했다.

그리고 바로 실행해봤다

 

 

First Code

 

function solution(n,m,section) {
    let maxNumber = Math.max(...section);
    let minNumber = Math.min(...section);
    let numberGap = maxNumber - minNumber + 1;

    if(numberGap<=m){
        return 1;
    } else {
        return Math.ceil(numberGap/m);
    }
};

.

위와 같이 코드를 짠 뒤 제출해보니 절반은 맞고 절반은 틀렸다.(26 / 50)

위의 논증을 반박할만한 반례 찾기가 필요했다. 반례를 찾다보니 한 개의 반례를 생각할 수가 있었다.

찾은 반례 => n = 8, m =2, section = [2,7,8] 

위와 같은 반례로 내 코드의 오류를 찾을 수 있었다. 롤러의 길이(m)가 작은 경우에는 색칠한 부분의 첫 칸과 끝 칸 사이에 색을 안칠하는 부분이 생길 수도 있었던 것이었다. 따라서 내 코드는 롤러의 길이가 작은 경우에 안칠해도 되는 부분의 색을 칠해 결과를 구하고 있던 것이었다.

 

 

Second Code

 

따라서 안칠해도 되는 부분을 원래의 결과값에서 빼주는 코드를 작성해봤다.

 

function solution2(n,m,section) {
    let maxNumber = Math.max(...section);
    let minNumber = Math.min(...section);
    let numberGap = maxNumber - minNumber + 1;
    let gap = 0;

    for(let i=0; i<section.length-1;i++){
        if(section[i+1]-section[i]-1>=m){
            gap += Math.floor((section[i+1]-section[i]-1)/m)
        }
    }

    if(numberGap<=m){
        return 1;
    } else if(numberGap>m && gap === 0){
        return Math.ceil(numberGap/m);
    } else {
        return Math.ceil(numberGap/m) - gap;
    }
};

 

위와 같이 코드를 짠 뒤에 실행시켜봤더니 첫 코드보다는 확실히 많이 맞았다.(40 / 50)

하지만 여전히 반례가 존재했고, 반례를 생각하다보니 위와 같은 방식으로는 성립이 안되는 반례들이 생각나서 아예 다른 방식으로 코드를 짜야했다.

 

 

Third Code

 

이번에는 아예 다른 방식으로 코드를 짰다. 앞선 두 코드에서는 전체적으로 색칠한 부분에 색칠이 안되어야 하는 부분을 빼주었다면 이번 코드는 배열의 인덱스 순서대로 색을 칠해보는 방식을 택했다.

조금 더 자세히 설명하자면 우선 전체 길이의 벽을 뜻하는 wallArr를 만들어주었다. section 배열은 색을 칠해야 하는 배열을 의미하기 때문에 wallArr에서 section과 일치하는 element는 색칠(coloring++)함과 동시에 롤러의 길이(m)만큼 배열을 지워줬고 일치하지 않는 부분은 그 element 부분만 지워주었다.

 

이렇게 코드를 짜게 된 것에는 여러 이유가 있다. 

 

나는 '색을 칠한 부분은 넘겨주고 그 다음부분부터 색을 칠해야할지 보자'라고 생각하고 그대로 코드에 옮기려고 했는데 이게 막상 해보니 생각보다 쉽지 않았다. 물론 코드는 쉽게 짰지만 생각했던 의도와는 다르게 작동했다.

예를 들어 forEach의 동작부분에 원본Arr를 바꿔주면 그 element는 바뀐 Arr의 요소를 쓰되 원래의 인덱스 순서를 따라갔다.

let arr = [1,2,3,4,5]

arr.forEach((el)=>{
	for(let i=0;i<m;i++){
    	arr.shift();
    }
}

위와 같이 작성했다고 치면 (문제와는 전혀 상관없는 코드이지만 이런 느낌으로 만들었었다) 첫 번째 반복에서 0번째 인덱스로 실행을 한 후 배열을 자르고 나면 두 번째 반복에서 잘라진 배열의 1번째 인덱스에서 실행이되고 ... 이렇게 반복되는 형태였다. 물론 이건 내가 원한 결과가 아니었다. 

 

또한 이와 비슷한 형태로 for문을 돌려 arr.length 만큼을 반복하는 반복문을 만들어봤다. 앞서 만든 반복문과는 다르게 내가 원하는 인덱스의 순서대로 동작되었지만 이 반복문의 문제점은 이전 동작부분에서 배열을 자르게되면 다음 동작부분에서는 잘라진 배열의 길이를 기준으로 반복문이 실행되기 때문에 원래 의도했던 반복문의 횟수보다 훨씬 더 적게 동작했다.

 

시행착오의 결과들

 

아무튼 이러한 이유로 내가 짠 코드가 완성되게 되었다.

 

function solution3(n,m,section){
    let wallArr = [];
    for(let i=0;i<n;i++){
        wallArr.push(i+1);
    }

    let coloring =0;

    for(let j=0;j<n;j++){
        // console.log("wallArr first element=>",wallArr[0])
        if(section.includes(wallArr[0])){
            coloring++;
            for(k=0;k<m;k++){
                wallArr.shift(); 
            }
        } else {
            coloring +=0;
            wallArr.shift();
        }
        // console.log("coloring=>",coloring)
        // console.log("wallArr=>",wallArr);

    }

    return coloring;
}

 

코드 실행결과는 성공적! 

하지만 만족스럽지는 못하다. 효율성도 너무 떨어지는 것 같고 코드도 뭔가 이쁘지가 않다.

 

실력이 많이 늘어 내가 생각하는 대로 코드는 짜게 되었다고 느끼지만 그걸 효율적으로 짜기에는 아직 실력이 턱 없이 부족하다는 생각을 자주 하게되는 것 같다. 효율성에 대해서 많이 생각하고 그렇게 짜도록 많이 시도해봐야 할 것 같다.

암튼 그래도 문제 정답! 뜨는 순간은 기분이 좋다.