💿 문제

문제 링크

💾 문제 요약

벽에 페인트칠을 가장 적게 하는 경우의 수는?

💿 풀이

벽 만들어주기

 const wall = Array(n).fill(true);

이미 칠해져 있는 구역 표시

for (let i=0; i<section.length; i++) {
        wall[section[i]-1] = false;
        falseCnt++; // 칠할 벽이 얼마나 있나 카운트
    }

배열을 순회하면서 인덱스 값이 false면 칠해줌.
벽을 칠할 때마다 falseCnt를 감소하면서 0이 되면 탈출.

while(falseCnt > 0) {
        if(wall[index] === false) {
            cnt++;
            for(let i=index; i<index+m && i < n; i++) {
                if(!wall[i]){
                    wall[i]=true;
                    falseCnt--;
                }
            }
        }
        index++;
}

💾 풀이 코드

function solution(n, m, section) {
    const wall = Array(n).fill(true);
    let index = 0;
    let cnt = 0;   
    let falseCnt = 0;

    for (let i=0; i<section.length; i++) {
        wall[section[i]-1] = false;
        falseCnt++;
    }
    
    while(falseCnt > 0) {
        if(wall[index] === false) {
            cnt++;
            for(let i=index; i<index+m && i < n; i++) {
                if(!wall[i]){
                    wall[i]=true;
                    falseCnt--;
                }
            }
        }
        index++;
    }
    return cnt;
}

💿 리마인더

반복문의 조건을 indexOf으로 할 경우 매번 배열을 순회해야함 -> 시간복잡도 상승

반복문의 범위 설정할 때 최대 범위 생각하기.

//example
for(let i=index; i<index+m; i++) // 어차피 i가 n보다 작은데 불필요한 범위까지 탐색할 가능성 있음.
  
for(let i=index; i<index+m && i < n; i++)  // && 연산자 추가해서 범위 좁혀줌.