[Programmers] 외벽 점검

김민석·2021년 12월 10일
0

프로그래머스

목록 보기
26/30

원형으로 된 외벽을 모두 점검하는데 드는 최소 인력을 구하는 문제이다.

스스로 풀다가 도저히 생각이 안나서 다른분이 작성한 블로그를 참고하였다.

문제해결 전략
원형으로 된 외벽을 점검하는데, 원형이므로 방향에 따라 두 지점 사이의 거리가 달라진다.

양 방향으로의 거리를 모두 고려하기 위해서 원형이던 기존의 벽을 일자로 편 후, 길이를 두배로 하고 기존 지점에 원래 길이를 더해 표현하면 된다.



문제의 원형 벽을 일자로 펴서 양방향 모두 고려하면 첫번째 직선이 나온다.
모두 양수로 치환해 줘서 두번째 직선으로 여길 수 있다.

그리고 보수가 필요한 지점이 k개 라고 했을 때 치환한 직선에서 연속된 k개의 지점을 보수하면 완료가 되는 것이다.

이제 보수를 해야할 인원을 선정하는 일이 남았다.
선정 순서도 중요하다. 4m와 2m를 처리할 수 있는 인원이 있다고 하자.

만약 4,2 순으로 선정했다면 10-13과 17-18을 맡으면 모든 외벽 수리가 완료된다.

하지만 2,4 순으로 선정했다면 두 인원만으로는 수리가 불가능하다.

위의 예시처럼 누구를 뽑는지도 중요하지만 뽑는 순서도 중요하다.

따라서 순열을 사용하여 어떤 순서로 작업하게 할 지 정하면 된다.

작업 순서를 정해 순차적으로 작업시켜 투입되는 인원이 가장 적은 사람 수를 찾아내면 된다.

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<int> weak, vector<int> dist) {
    int answer = -1;
    
    vector<int> v;
    v = weak;
    for(int i=0;i<weak.size();i++)
        v.push_back(weak[i] + n);
    
    sort(dist.begin(), dist.end());
    
    do{
        for(int i=0;i<weak.size();i++){
            int start = v[i];
            int end = v[i+weak.size()-1];
            for(int j=0;j<dist.size();j++){
                start += dist[j];
                if(start >= end){
                    if(answer == -1)
                        answer = j+1;
                    else
                        answer = min(answer, j+1);
                    break;
                }
                
                int next = -1;
                for(int k = i+1;k<v.size();k++){
                    if(v[k] > start){
                        next = k;
                        break;
                    }
                }
                if(next != -1)
                    start = v[next];
                else
                    break;
            }
        }
    }while(next_permutation(dist.begin(), dist.end()));
    
    return answer;
}

보완할 점
다음 지점(next)을 찾을 때 반복문을 통해 찾아냈다. -> O(n)
다음 지점 찾기를 이분탐색으로 한다면 더 짧은 시간에 찾아낼 수 있다. -> O(logN)
이분탐색은 upper_bound(시작, 끝, 찾을값)을 통해 할 수 있다.
upper_bound는 찾을값이 유무가 아닌 찾을값보다 큰 값의 첫 위치를 찾을때 사용하므로 넣을 값의 위치를 찾아낼 때 사용할 수 있다.

참고
https://yjyoon-dev.github.io/kakao/2021/01/04/kakao-wallcheck/
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=occidere&logNo=221045300639

출처
https://programmers.co.kr/learn/courses/30/lessons/60062#

profile
김민석의 학습 정리 블로그

0개의 댓글