덧칠하기 - 161989

문제 설명
어느 학교에 페인트가 칠해진 길이가 n미터인 벽이 있습니다. 벽에 동아리 · 학회 홍보나 회사 채용 공고 포스터 등을 게시하기 위해 테이프로 붙였다가 철거할 때 떼는 일이 많고 그 과정에서 페인트가 벗겨지곤 합니다. 페인트가 벗겨진 벽이 보기 흉해져 학교는 벽에 페인트를 덧칠하기로 했습니다.

넓은 벽 전체에 페인트를 새로 칠하는 대신, 구역을 나누어 일부만 페인트를 새로 칠 함으로써 예산을 아끼려 합니다. 이를 위해 벽을 1미터 길이의 구역 n개로 나누고, 각 구역에 왼쪽부터 순서대로 1번부터 n번까지 번호를 붙였습니다. 그리고 페인트를 다시 칠해야 할 구역들을 정했습니다.

벽에 페인트를 칠하는 롤러의 길이는 m미터이고, 롤러로 벽에 페인트를 한 번 칠하는 규칙은 다음과 같습니다.

롤러가 벽에서 벗어나면 안 됩니다.
구역의 일부분만 포함되도록 칠하면 안 됩니다.
즉, 롤러의 좌우측 끝을 구역의 경계선 혹은 벽의 좌우측 끝부분에 맞춘 후 롤러를 위아래로 움직이면서 벽을 칠합니다. 현재 페인트를 칠하는 구역들을 완전히 칠한 후 벽에서 롤러를 떼며, 이를 벽을 한 번 칠했다고 정의합니다.

한 구역에 페인트를 여러 번 칠해도 되고 다시 칠해야 할 구역이 아닌 곳에 페인트를 칠해도 되지만 다시 칠하기로 정한 구역은 적어도 한 번 페인트칠을 해야 합니다. 예산을 아끼기 위해 다시 칠할 구역을 정했듯 마찬가지로 롤러로 페인트칠을 하는 횟수를 최소화하려고 합니다.

정수 n, m과 다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section이 매개변수로 주어질 때 롤러로 페인트칠해야 하는 최소 횟수를 return 하는 solution 함수를 작성해 주세요.

제한사항
1 ≤ m ≤ n ≤ 100,000
1 ≤ section의 길이 ≤ n
1 ≤ section의 원소 ≤ n
section의 원소는 페인트를 다시 칠해야 하는 구역의 번호입니다.
section에서 같은 원소가 두 번 이상 나타나지 않습니다.
section의 원소는 오름차순으로 정렬되어 있습니다.

입출력 예
n m section result
8 4 [2, 3, 6] 2
5 4 [1, 3] 1
4 1 [1, 2, 3, 4] 4

---

설계

덧칠해야하는 첫부분 section[0]을 기준으로 m - 1 (칠하는 부분을 포함하기에 - 1) 하고 answer++로 카운팅하고 덧칠해야하는 섹션보다 인덱스보다 크면 그다음 섹션과 비교한다. 이 동작을 반복한다.

 

구현

#include <string>
#include <vector>

using namespace std;

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

---

리펙토링

#include <vector>

using namespace std;

// 매개변수 section을 참조자(&)로 받아 불필요한 메모리 복사를 방지합니다.
int solution(int n, int m, const vector<int>& section) {
    int answer = 0;       // 롤러로 칠한 총 횟수
    int painted_end = 0;  // 롤러로 칠한 가장 '오른쪽(마지막) 끝 지점'을 저장

    // section 배열을 처음부터 끝까지 한 번에 순회합니다.
    for (int i = 0; i < section.size(); i++) {
        
        // 만약 현재 확인하는 구역(section[i])이 
        // 이전에 칠했던 롤러의 범위(painted_end)를 벗어났다면? -> 새로 칠해야 합니다!
        if (section[i] > painted_end) {
            
            answer++; // 페인트칠 횟수 1 증가
            
            // 롤러의 왼쪽 끝을 section[i]에 맞춰서 칠합니다.
            // 따라서 롤러가 덮은 마지막 위치는 '시작 지점 + 롤러의 길이 - 1'이 됩니다.
            // 이 위치를 다음 탐색을 위해 갱신해 줍니다.
            painted_end = section[i] + m - 1; 
        }
        // section[i]가 painted_end보다 작거나 같다면,
        // 이전에 칠할 때 이미 같이 칠해졌다는 뜻이므로 무시하고 넘어갑니다.
    }

    return answer;
}

💡 주요 리팩토링 포인트

1. 초기화 구문과 메인 루프의 병합 (코드 간소화) 기존 코드에서는 section[0]을 미리 한 번 칠하고 시작(answer++)한 뒤, for문을 i = 1부터 돌렸습니다. 이 방식도 좋지만, CurrentLoc의 초기값을 0으로 설정하고 for문을 0부터 돌게 만들면 예외 처리나 초기 설정 코드 없이 반복문 하나로 모든 로직을 깔끔하게 통합할 수 있습니다.
2. 직관적인 변수명 사용 (가독성 향상) CurrentLoc(현재 위치)라는 이름보다는 painted_end(페인트칠이 끝난 지점) 또는 limit처럼 **"여기까지는 이미 칠해져 있다"**는 의미를 명확하게 담는 변수명이 알고리즘의 의도를 더 잘 보여줍니다.
3. C++ 매개변수 참조자(&) 활용 (성능 팁) 프로그래머스 기본 템플릿은 vector<int> section으로 값을 '복사(Call by Value)'해서 넘겨줍니다. 하지만 section의 크기가 최대 100,000이므로, 복사 비용을 줄이기 위해 const vector<int>& section처럼 **'상수 참조(Call by Reference)'**로 변경해주면 메모리와 속도 면에서 미세한 이점을 얻을 수 있습니다. (코딩 테스트 플랫폼에서 함수 시그니처 수정이 가능하다면 권장하는 방법입니다.)

---

회고

이 문제에서 알고리즘적으로 큰 리펙토링은 없었다. 하지만 그리디 알고리즘을 알고 사용하진 않았지만, 그리디 알고리즘을 알 수 있었다.

 

그리디 알고리즘

현재 상황에서 지금 당장 가장 좋아 보이는 것만 탐욕적으로 고르는 방법.

 

그리디 알고리즘은 언제 성공할까? (정당성 증명)

그리디 알고리즘은 생각하기 쉽고 코드도 간결하지만, 항상 전체의 정답을 보장하지는 않습니다. 현재 최선의 선택이 나중에는 독이 될 수도 있기 때문입니다.

따라서 코딩 테스트에서 그리디를 사용하려면, 내 탐욕적인 선택이 최종적으로도 정답이 된다는 정당성을 떠올려야 합니다. 보통 다음 두 가지 조건이 만족될 때 그리디가 완벽하게 작동합니다.

1. 탐욕적 선택 속성 (Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조 (Optimal Substructure): 문제 전체에 대한 최적의 해답이, 부분 문제에 대해서도 최적의 해답이다.

앞서 푸신 페인트칠 문제를 예로 들면, "가장 먼저 나타난 벗겨진 구역부터 롤러를 덮는다"는 현재의 최선의 선택이, 뒤쪽 벽을 칠하는 상황을 방해하거나 페인트칠 횟수를 늘리지 않기 때문에 그리디로 완벽히 풀린 것입니다.