♡̈ 05. 프로그래머스:: 덧칠하기

 

문제가 조금 헷갈려서 조건만 나누어 정리하고,

어떻게 사고할지에 대한 부분을 후에 생각했다.

 

문제 조건

· 길이 n 벽을 1미터 구역으로 나누어 번호를 붙임
· 다시 칠해야할 구역이 section이 됨
· 롤러 길이는 m 미터
· 최소한의 롤러 칠 횟수

 

어떻게 최소 롤러를 구할 수 있을까?

 

1. 현재 위치에서 최대한 롤러를 덮어야 함
2. 롤러가 덮을 수 있는 구역의 마지막 위치를 계산함
3. 덮을 수 있는 구역은 모두 건너뛰고 count를 계산함

 

function solution(n, m, section) {
    let count = 0;
    let i = 0;

    while (i < section.length) {
        const end = section[i] + m - 1;
        count++;

        while (i < section.length && section[i] <= end) {
            i++;
        }
    }

    return count;
}

 

개인적으로 중첩 반복문이라 시간복잡도 면에서 걱정이 많이 됐는데

다행히 통과될 수 있었다.

 

다른 사람의 코드를 확인해보자.

function solution(n, m, sections) {
    var answer = 0;
    var painted = 0;
    for(var section of sections) {
        if(painted < section) {
            answer++;
            painted = section + m - 1;
        }
    }
    return answer;
}

 

아무래도 반복문이 하나로 줄었으니 더 괜찮아보인다.

 

근데 여기서 신기한건, 두 코드의 성능이 크게 차이나지 않는다는 것이다.

왜냐면 내 코드는 내부 반복문과 외부 반복문이 상호 보완적이기 때문이다.

 

자세히 보면 각 요소를 한번씩만 처리하게되며,

section.length에 도달하기까지 내부 루프가 반복되지 않기 때문이다.

 

하지만 그럼에도 불구하고

다른 사람의 코드가 가독성이 더 좋아보인다.

 

근데 for-of이 좀 어색해서 정리해봤다.

---

for...of	배열 및 이터러블 객체 순회	루프 중단이 가능함	빠름
forEach	배열 순회	중단할 수 없음	빠름
for...in	객체의 열거 가능한 속성을 순회할 때 사용	배열 순회시 인덱스가 문자열 처리므로 비효율	느림