[알고리즘 || 프로그래머스] 덧칠하기

갈 수록 시간이 엄청 걸리는데.. 

기분탓인가....

전에 비슷한 문제 풀었던거 같은데, 

풀면서 엄청 헷갈려서 애먹었다... 

풀 수 있을 거 같은데 잘 안돼서 오래 잡고 있었다.

(오전에 2시간 보고 오후에 1시간 걸려서 풀어냈다,)

 

function solution(n, m, sections) {
    let allSection = new Array(n + 1).fill(0);
    Array.from(sections, x => allSection[x] = -1);

    let count = 0;
    sections.map(s => {
        if (allSection[s] === -1) {
            count++;
            for (let i = s; i < s + m; i++) {
                allSection[i] += 1;
            };
        }
    })
    return count;
}

 

후. 처음엔 m 만큼 n 의 구간을 나눠서 하려고 했는데, 딱떨어지지 않는 부분도 있고 해서 더 헷갈렸던 것 같다.

 

먼저 n 의 개수 + 1 만큼 0이 들어있는 배열을 만든다.

그리고 from 메서드를 이용해 section 에 들어있는 곳, 즉 페인트가 칠해져야 하는 구간은 -1 로 바꿔줬다.

 

그럼 예시 1 의 경우

 

[
  0,  
  0, -1, -1, 0,
  0, -1,  0,  0
]

이런 모양의 배열이 만들어진다.

 

sections 를 map 을 이용해 페인트를 칠해보자.

 

section 즉, 시작하는 곳이 -1 인 경우에만 페인트를 칠한다.

=> index 2가 -1 이므로 => for 문으로 2, 3, 4, 5 구간이 칠해진다.

=> index 3 은 0 이 되었으므로 건너뛴다.

=> index 6 d은 -1 이므로 페인트를 칠한다.

for 문이 작동할 때마다 count 를 세어준다.

 

칠할 칸이 있을 때만 for 문이 돌고, count 에 +1 을 해주기 때문에, 최소한의 count 가 구해진다.

n 의 범위가 10만개인걸 감안하면 속도도 만족스럽다.