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

덧칠하기

문제 링크

덧칠하기

분석

section배열의 위치를 의미하는 요소에 롤러로 페인트 칠을 해야합니다.
롤러는 한번에 m만큼의 롤러를 칠할 수 있고, 한번 칠하기 시작하면 떼지 않고 쭉 칠해야합니다.
이때 롤러로 페인트 칠하는 최소 횟수를 구하는 문제입니다.

section은 중복된 값 없이 요소가 1개 이상이며, 오름차순으로 정렬 되어있습니다.

n과 m은 1 이상입니다.

풀이

#include <vector>

using namespace std;

int solution(int n, int m, vector<int> section) {
    int answer = 1;
    
    int rollerStart = section[0];
    
    for (int i = 1; i < section.size(); ++i)
    {   
        if (section[i] - rollerStart >= m)
        {
            rollerStart = section[i];
            ++answer;
        }
    }
    
    return answer;
}

rollerStart은 롤러로 칠하려는 페인트 칠의 시작하는 위치입니다.

section을 순회하면서, 롤러가 시작한 위치부터 현재 칠해야하는 위치까지 칠할 수 있는지 확인합니다.
칠 할 수 없는 위치라면 롤러의 시작 위치를 변경하며, 롤러가 칠하는 횟수를 증가시킵니다.

만약 section의 크기와 m, n이 1일 경우 반복문은 실행되지 않고, 바로 answer의 값이 반환됩니다.

성능 요약

시간 복잡도는 section을 순회하므로, $O(n)$입니다.

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 1 〉 통과 (0.16ms, 4.8MB)
테스트 2 〉 통과 (0.20ms, 5.57MB)
테스트 3 〉 통과 (0.16ms, 4.76MB)
테스트 4 〉 통과 (0.01ms, 4.19MB)
테스트 5 〉 통과 (0.24ms, 4.73MB)
테스트 6 〉 통과 (0.01ms, 4.16MB)
테스트 7 〉 통과 (0.01ms, 4.14MB)
테스트 8 〉 통과 (0.09ms, 4.41MB)
테스트 9 〉 통과 (0.01ms, 3.58MB)
테스트 10 〉 통과 (0.13ms, 4.43MB)
테스트 11 〉 통과 (0.01ms, 4.11MB)
테스트 12 〉 통과 (0.10ms, 4.51MB)
테스트 13 〉 통과 (0.30ms, 5.83MB)
테스트 14 〉 통과 (0.24ms, 5.04MB)
테스트 15 〉 통과 (0.01ms, 4.21MB)
테스트 16 〉 통과 (0.07ms, 4.22MB)
테스트 17 〉 통과 (0.20ms, 4.78MB)
테스트 18 〉 통과 (0.01ms, 4.2MB)
테스트 19 〉 통과 (0.17ms, 4.74MB)
테스트 20 〉 통과 (0.14ms, 4.53MB)
테스트 21 〉 통과 (0.18ms, 4.68MB)
테스트 22 〉 통과 (0.22ms, 4.85MB)
테스트 23 〉 통과 (0.23ms, 4.99MB)
테스트 24 〉 통과 (0.01ms, 3.67MB)
테스트 25 〉 통과 (0.15ms, 4.73MB)
테스트 26 〉 통과 (0.08ms, 4.4MB)
테스트 27 〉 통과 (0.05ms, 4.24MB)
테스트 28 〉 통과 (0.01ms, 4.21MB)
테스트 29 〉 통과 (0.01ms, 4.14MB)
테스트 30 〉 통과 (0.01ms, 4.14MB)
테스트 31 〉 통과 (0.01ms, 4.13MB)
테스트 32 〉 통과 (0.01ms, 4.2MB)
테스트 33 〉 통과 (0.01ms, 3.67MB)
테스트 34 〉 통과 (0.01ms, 4.21MB)
테스트 35 〉 통과 (0.13ms, 4.62MB)
테스트 36 〉 통과 (0.01ms, 4.13MB)
테스트 37 〉 통과 (0.08ms, 4.29MB)
테스트 38 〉 통과 (0.01ms, 4.21MB)
테스트 39 〉 통과 (0.08ms, 4.51MB)
테스트 40 〉 통과 (0.01ms, 4.13MB)
테스트 41 〉 통과 (0.27ms, 5.68MB)
테스트 42 〉 통과 (0.01ms, 4.14MB)
테스트 43 〉 통과 (0.01ms, 4.2MB)
테스트 44 〉 통과 (0.01ms, 4.2MB)
테스트 45 〉 통과 (0.22ms, 5.04MB)
테스트 46 〉 통과 (0.04ms, 3.8MB)
테스트 47 〉 통과 (0.23ms, 5.23MB)
테스트 48 〉 통과 (0.10ms, 4.27MB)
테스트 49 〉 통과 (0.12ms, 4.59MB)
테스트 50 〉 통과 (0.16ms, 4.99MB)