프로그래머스 - greedy(체육복, 조이스틱, 큰 수 만들기, 구명보트, 섬 연결하기, 단속카메라)

문제 링크 - https://programmers.co.kr/learn/courses/30/parts/12244

👀문제이해 및 풀이방법

그리디 문제이다. 상당히 난이도가 높았다.


백준에서 최소 스패닝 트리 라던지, 스위핑, 투포인터 등등으로 알고리즘을 분류해 놓은것을 다 그리디로 묶어놓았다

문제 퀄리티는 상당히 좋아서 풀때는 스트레스였지만 풀고나서는 많이 배운듯한 느낌이 들었다.

1,2번은 비교적 쉽게 풀리는 문제이고 3번 큰 수 만들기 문제같은 경우 그냥 작은거부터 없애는게 아니라 앞이 뒤보다 작을경우 삭제하는 방식으로 풀었다.

4번 구명보트 문제는 투포인터를 쓰지 않으면 시간복잡도가 되지 않으므로 결국 아이디어를 찾아보고 풀게 되었다

5번은 MST의 기본적인 유형이라 크루스칼을 사용하여 풀었다 다만 다른사람의 풀이를 보니 난 pq를 만들어서 데이터를 넣었는데 그냥 정렬해서 사용한걸 보고 또 간만에 유니온파운드를 사용하여 배우는 점들이 있었다.

6번같은 경우에는 스위핑 문제인데 역시 스위핑문제는 모든 유형중에 가장 어렵다 방법이 생각나지 않으면 알고리즘의 동작방법을 알아도 전혀 풀수가 없는데

결국 그냥 2중for문 형식으로 풀어제꼈다. 풀고 답을보니 끝나는 시간을 정렬하여 체크했는데 스위핑 문제들은 방법이 생각나지않으면 끝없이 생각이 안나는지라 많은 연습이 필요하다고 느꼈다.

코드는 직접 짠 코드를 올리고 더 좋은 방식은 직접 생각해보시길 바란다!👍

📝코드

1 체육복

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer=0;
    vector<int> get(n+2,1);
    for(int i : lost)
        get[i]--;
    for(int i : reserve)
        get[i]++;
    for(int i=1;i<=n;i++){
        if(get[i]==2){
            if(i>1 && !get[i-1])
                get[i-1]++;
            else if(i<n && !get[i+1])
                get[i+1]++;
            get[i]--;
        }
    }
    for(int b : get)
        answer+=b;
    return answer-2;
    
}

2 조이스틱

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int solution(string name) {
    int answer = 0;
    string str="";
    for(int i=0;i<name.size();i++)
        str+='A';
    int cur = 0,tmp,sol_tmp;
    while(str!=name){
        tmp=0;
        if(str[cur]==name[cur]){
            while(true){
                tmp++;
                if(str[(cur+tmp)%name.size()]!=name[(cur+tmp)%name.size()]){
                    cur=(cur+tmp)%name.size();
                    break;
                }
                else if(str[(cur-tmp+name.size())%name.size()]!=name[(cur-tmp+name.size())%name.size()]){
                    cur=(cur-tmp+name.size())%name.size();
                    break;
                }
            }
        }
        sol_tmp=(int)(name[cur]-str[cur]);
        answer+=min(sol_tmp,26-sol_tmp)+tmp;
        str[cur]=name[cur];
    }
    return answer;
}

3 큰 수 만들기

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

string solution(string number, int k) {
    for(int i=0;i<k;i++){
        for(int i=0;i<number.size();i++){
            if(i==number.size()-1)
                number.erase(number.begin()+i);
            else if(number[i]<number[i+1]){
                number.erase(number.begin()+i);
                break;
            }
        }
    }
    return number;
}

4 구명보트

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(int& a,int& b){
    return a>b;
};
int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(),people.end(),compare);
    int left=0,right=people.size()-1;
    while(left<right){
        if(people[left]+people[right]<=limit){
            left++;
            right--;
        }
        else{
            left++;
        }
        answer++;
    }
    if(left==right)
        answer++;
    return answer;
}

5 섬 연결하기

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct _node{
    int a,b,cost;
};
struct compare{
    bool operator()(_node& a,_node& b){
        return a.cost>b.cost;
    }
};
class test5{
private:
    vector<vector<int>> cost;
    vector<int> set;
    int N;
public:
    test5(vector<vector<int>>& c,int& n):cost(c),N(n){
        set.resize(N,-1);
    }
    int find(int a){
        if(set[a]==-1)
            return a;
        return set[a] = find(set[a]);
    }
    bool merge(int a,int b){
        int pa= find(a);
        int pb= find(b);
        if(pa==pb)
            return false;
        set[pb]=pa;
        return true;
    }
    int cruscal(){
        int sol=0;
        priority_queue<_node,vector<_node>,compare> pq;
        for(int i=0;i<cost.size();i++)
            pq.push({cost[i][0],cost[i][1],cost[i][2]});
        int cnt=0;
        _node cur;
        while(cnt!=N-1){
            cur = pq.top();
            pq.pop();
            if(merge(cur.a,cur.b)){
                cnt++;
                sol+=cur.cost;
            }
        }
        return sol;
    }
};
int solution(int n, vector<vector<int>> costs) {
    test5 t5(costs,n);
    return t5.cruscal();
}

6 단속카메라

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int INF=1000000;
struct compare{
    bool operator()(vector<int>& a,vector<int>& b){
        return a[0]>b[0];
    };
};
int solution(vector<vector<int>> routes) {
    int answer = 0;
    priority_queue<vector<int>,vector<vector<int>>,compare> pq;
    for(int i=0;i<routes.size();i++)
        pq.push(routes[i]);
    int all_cnt=0,cnt=0,time=pq.top()[0],end_time=INF;
    while(all_cnt!=routes.size()){
        while(pq.top()[0]==time){
            end_time=min(end_time,pq.top()[1]);
            pq.pop();
            cnt++;
        }
        if(end_time==time){
            answer++;
            all_cnt+=cnt;
            cnt=0;
            end_time=INF;
        }
        time++;
    }
    return answer;
}