[프로그래머스] Lv.01 연습문제 덧칠하기 (JavaScript)

문제설명

어느 학교에 페인트가 칠해진 길이가 n미터인 벽이 있다고 한다. 학교에서는 페인트가 벗겨진 벽에 페인트를 덧칠하고자 한다. 넓은 벽 전체에 페인트를 새로 칠하는 대신, 구역을 나누어 일부만 페인트를 새로 칠하려고 한다.

이를 위해 벽을 1미터 길이의 구역 n개로 나누고, 각 구역에 왼쪽부터 순서대로 1번부터 n번까지 번호를 붙이고, 이를 기반으로 페인트를 다시 칠해야 할 구역들을 정했다. 벽에 페인트를 칠하는 룰러의 길이는 m미터 이고 벽에 페인트를 한 번 칠할 때 룰러가 벽에서 벗어나면 안되고 구역의 일부분만 포함되도록 칠하면 안된다고 한다.

한 구역에 페인트를 여러 번 칠해도 되고 다시 칠해야 할 구역이 아닌 곳에 페인트를 칠해도 되지만 다시 칠하기로 정한 구역은 적어도 한 번 페인트 칠을 하면서 페인트칠을 하는 횟수를 최소화하고자 한다.

벽과 룰러의 길이를 담고 있는 변수 n,m과 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section이 주어질 때 페인트칠해야 하는 최소 횟수를 구하면 된다.

※제한사항

 - 1 <= m <= n <= 100,000

 - 1 <= section의 길이 <= n

 - 1 <= section의 원소 <= n

 - section의 원소는 오름차순으로 정렬되어 있다.

 - section에서 같은 원소가 두 번 이상 나타나지 않는다

풀이

문제 설명에서 페인트칠을 최소화해야 하지만 중복해서 칠해도 된다고 되어 있다. 문제 예시를 봤을 때 section이 [2,3,6]이고 n=8, m=4일 때 2에서5까지 한 번 칠하고 3에서6까지 한 번해서 총 2번의 페인트칠을 하는 것으로 나와있다. 그러면 처음 칠해야 되는 부분에서 페인트칠 횟수를 체크해주고 그 숫자에 +m을 했을 때 다시 횟수를 체크해주는 것과 똑같은 것이 아닌가 생각하였다. 그리고 이를 바탕으로 코드를 작성해봤는데 생각과 일치했다.

아래 코드는 처음 시도한 코드이다.

function solution(n, m, section) {
    var answer = 0;
    
    // n만큼 반복을 돌리고 그 안에서 section 데이터를 조회해서 횟수를 체크한다
    for(let i = 1; i <= n; i++){
        section.map((data) => {
            if(data === i){
                answer++
                i+=m // 횟수를 중복해서 증가하면 안되므로 m만큼 증가시켜 주었다
            }
        })
    }
    
    return answer;
}

 

위에 코드를 작성했을 때 코드는 정상적으로 작동했다. 하지만 이중 반복문을 돌려서 인지 일부 테스트에서 시간 초과 문제가 발생했다. 그래서 시간을 줄일 방법을 생각해봐야 했는데, 코드를 다시 살펴보니 굳이 section을 반복문을 돌릴 필요가 없을 거 같았다. 반복문을 돌리지 않고 section의 데이터만 조회해도 충분히 가능할거 같아 이에 맞게 코드를 수정했고 정답이였다.

아래는 수정한 코드이다.

function solution(n, m, section) {
    var answer = 0;
    
    // section에서 i가 있는지 직접 조회하는 방법으로 수정
    for(let i = 1; i <= n; i++){
    	// section에 데이터가 있는지 확인
        if(section.includes(i)){
            answer++
            i+=m-1 // 다음 반복 시 +1이 되기 때문에 m-1을 더해줘야 한다
        }
    }
    
    return answer;
}

 

문제를 풀고 나서 다른 사람들의 풀이도 살펴보았는데, 내 코드랑은 다소 다른 부분이 있었다. 내 경우 n번만큼 반복문을 돌렸는데 여기서는 section의 요소만 반복문을 돌리는 방식으로 코드가 작성되어 있었다. 문제를 풀 때 n를 사용해야 한다는 생각에 n번만큼 반복을 돌렸는데 다른 사람들의 코드를 보고나니 그럴 필요가 없었던 것이다;

아래는 다른 사람들이 작성한 코드이다.

unction solution(n, m, sections) {
    var answer = 0;
    var painted = 0;
    
    // 여기서는 section의 요소만 반복을 돌린다
    for(var section of sections) {
        if(painted < section) {
            answer++;
            painted = section+m-1;
        }
    }
    return answer;
}