덧칠하기

문제

문제 해석

1. 파라미터 해석

    - n미터인 벽(1미터 길이의 구역 n개, 1번부터 n번까지 번호) 

    - m미터 길이의 롤러(한번에 m미터만큼 칠해야 함)

    - 정수 배열 section : 다시 페인트를 칠하기로 정한 구역들의 번호가 담겨있음. 

2. 칠하는 규칙

    - 롤러가 벽에서 벗어나면 안 된다.

    - 구역의 일부분만 포함되도록 칠하면 안 된다.(한 번에 길이만큼 칠함)

    - 이미 칠해진 구역을 다시 칠할 수 있다.

3. 반환해야 할 답의 뜻

    - 롤러로 칠하는 최소 횟수

 

4. 문제 풀이 고안

    - 벽의 길이가 최대 100,000이므로 O(N^2)으로 순회를 해도 괜찮다고 판단했다.

    - 칠했는지 여부를 저장하는 배열(vector<bool> Wall)을 하나 만든다 : 벽을 배열로 가지고 이 배열에 칠해야 하는 곳을 찾아서 거기부터 칠하기 시작하므로

    - 벽의 크기를 N으로 설정하고 이미 전부 칠해져 있다 가정하고 true로 채운다.

    - section을 순회하며 칠해야 할 벽을 false로 바꿔준다.(section에 저장된 번호는 1부터 시작함에 유의)

    - Wall을 순회하는 반복을 시작한다.

        - 이미 칠해진 벽(true)이면 다음 벽을 조회한다.

        - 위를 통과하지 못했다면 안 칠해진 벽이므로 해당 벽부터 M만큼 반복하며 벽을 칠해준다.(true로 변경한다)

        -> 풀이 대체 : fill을 이용하여 해당 벽부터 M만큼의 벽을 칠해준다.(단, M만큼의 벽이 최대 벽 길이보다 길 수 있으므로 주의가 필요함)

        - 통과하지 못했으면 칠을 한 것이므로 answer를 증가시킨다.

 

#include <vector>
#include <algorithm>

using namespace std;

int solution(int N, int M, vector<int> Section) {
    int Answer = 0;
    // 페인트가 칠해진 길이가 n미터인 벽
    // 학교는 벽에 페인트를 덧칠하기로
    // 구역을 나누어 일부만 페인트를 새로 칠
    // 벽을 1미터 길이의 구역 n개로 나누고
    // 각 구역에 왼쪽부터 순서대로 1번부터 n번까지 번호
    // 페인트를 다시 칠해야 할 구역들을 정했습니다.
    // 벽에 페인트를 칠하는 롤러의 길이는 m미터
    // 롤러로 벽에 페인트를 한 번 칠하는 규칙
    // 1. 롤러가 벽에서 벗어나면 안 됩니다.
    // 2. 구역의 일부분만 포함되도록 칠하면 안 됩니다.
    // 3. 한 구역에 페인트를 여러 번 칠해도 되고 다시 칠해야 할 구역이 아닌 곳에 페인트를 칠해도 되지만
    //    다시 칠하기로 정한 구역은 적어도 한 번 페인트칠을 해야함.
    // 롤러로 페인트칠해야 하는 최소 횟수 return
    // 정수 n, m과 다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section이 매개변수
    
    // 벽은 1~n번까지의 번호를 지닌다.
    vector<bool> Wall(N);
    fill(Wall.begin(), Wall.end(), true);
    for(int Number : Section)
    {
        // 칠해야 할 벽을 false로 바꿔준다.
        Wall[Number - 1] = false;        
    }
    
    size_t WallSize = Wall.size();
    for(size_t IDX = 0; IDX < WallSize; ++IDX)
    {
        if(Wall[IDX])
        {
           continue; 
        }
        
        size_t TargetBegin = IDX;
        size_t TargetEnd = IDX + M;
        if(TargetEnd > WallSize) 
        {
            TargetEnd = WallSize;
        }
        
        fill(Wall.begin() + TargetBegin, Wall.begin() + TargetEnd, true);
        //for(size_t Target = IDX; Target < (IDX + M) && Target < WallSize; ++Target)
        //{
        //    Wall[Target] = true;
        //}
        ++Answer;
    }
    
    return Answer;
}

 

다른 사람의 풀이

1. section에 담긴 값과 오름차순이 되어 있는 특성을 이용하여 변수 2개(pivot, section에 담긴 각각의 값)로 O(N)으로 풀이

 

 

회고

1. vector<bool>로 굳이 기록을 하지 않아도 됐다는 점에서(다른 사람은 해당 방법을 사용하지 않고 풀었으므로 메모리 절약 관점에서라도) 다른 방법도 생각할 필요가 있는 것 같다.