프로그래머스 [연습문제 / 덧칠하기](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 덧칠하기

---

문제 링크: 문제 보기

문제 설명:

길이가 n인 벽이 주어질 때, 특정 구간(section)을 칠해야 합니다. 롤러의 길이는 m이며, 최소한의 롤러 사용 횟수로 벽을 모두 칠하는 방법을 구하는 문제입니다.

---

문제 해결 코드

#include <string>
#include <vector>

using namespace std;

int solution(int n, int m, vector<int> section) {
    int answer = 0;
    int lastPainted = 0; // 마지막으로 롤러를 사용한 위치
    
    for (int i = 0; i < section.size(); i++) {
        if (section[i] > lastPainted) { // 롤러를 새로 칠해야 하는 경우
            answer++; 
            lastPainted = section[i] + m - 1; // 롤러가 칠할 수 있는 범위 갱신
        }
    }
    
    return answer;
}

---

코드 설명

• 핵심 알고리즘: 그리디 알고리즘을 활용하여 최소한의 롤러 사용 횟수로 벽을 칠합니다. 가장 앞쪽부터 롤러를 사용하며, 최대한 넓은 영역을 덮는 방식으로 해결합니다.
• 구현 세부사항:
• lastPainted: 마지막으로 롤러를 사용한 위치를 저장하여, 불필요한 롤러 사용을 방지합니다.
• section[i] > lastPainted인 경우, 해당 위치부터 새롭게 롤러를 사용하고 lastPainted를 업데이트합니다.
• 시간 복잡도 분석:
• 롤러 사용 횟수 탐색: O(s), 여기서 s는 section의 크기
• 총 시간 복잡도: O(s) (선형 탐색)

---

결과

이 코드는 최소한의 롤러 사용 횟수를 계산하여 최적의 칠하기 방법을 찾습니다. 불필요한 연산을 줄이고 선형 탐색으로 해결하여 높은 효율성을 가집니다.

다른 접근 방식으로는 deque를 이용해 남은 구간을 효율적으로 탐색하는 방법이 있으며, 이는 특정 케이스에서 성능을 더 최적화할 수 있습니다.