[프로그래머스] 카카오 외벽 점검 c++

programmers.co.kr/learn/courses/30/lessons/60062

코딩테스트 연습 - 외벽 점검

 

 

-기본적인 아이디어.

순열을 이용하여 dist배열의 모든 경우의 수에 대하여

weak에 배치하여 최솟값을 구한다.

 

-세부적인 아이디어.

거리 계산을 편하게 하기 위해 weak 벡터에 n+weak[i]를 push_back하여

원형의 효과가 나게 선형으로 구현한다.

dist의 순열을 반복하기 위해 <algorithm>에 구현된 prev_permutation()를 이용한다.

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool comp(int a, int b) {
    return a > b;
}



//https://programmers.co.kr/learn/courses/30/lessons/60062
int solution(int n, vector<int> weak, vector<int> dist) {
    
    int answer =10000;
    int ws = weak.size();
    int ds = dist.size();
    sort(dist.begin(),dist.end(),comp);
    for(int i=0; i<ws; i++) weak.push_back(n+weak[i]);
    
    
    int std,stdist,cn,total,sw;
   
    
    for(int stw=0; stw<ws; stw++)
    {
        
        while(1)
        {
            std=0;
            stdist=dist[0];
            cn=0;
            total=0;
            sw=0;
            for(int i=stw; i<ws+stw; i++)
            {
                
                if(cn==0)
                {
                    cn++;
                    continue;
                }
                
                if(stdist-(weak[i]-weak[i-1])<0)
                {
                    i--;
                    cn=0;
                    total++;
                    if(total+1>=answer||total==ds) 
                    {
                        sw=1;
                        break;
                    }   
                    std++;
                    stdist=dist[std];
                }
                else
                {
                    cn++;
                    stdist=stdist-(weak[i]-weak[i-1]);
                }
                
            }
            
            
            if(sw==0&&answer>total+1)
            {
                answer=total+1;
            }
            
            if(!prev_permutation(dist.begin(),dist.end()))
            {
                break;
            }
        }
        
        
    }
    
    
   if(answer==10000) answer=-1;
    
    return answer;
}

 

-피드백

처음에는 확실한 알고리즘이 있을 줄 알아서 시간을 많이 허비했다.

모든 경우의 수에 대하여 순열로 코딩을 하려하니 실력이 부족했다;;

덕분에 permutation 함수를 알게되었다. (너무간편)

지금 코드에서 좀 더 효율적으로

중복을 조금 더 추려내면 시간이 더 줄어들것 같다.

 

외벽 점검 실행시간