프로그래머스 알고리즘 고득점 Kit - 탐욕법(Greedy)

체육복

- 체육복 도난당한 학생 리스트/여벌 체육복 가져온 학생 리스트 주어짐

- 인접한 번호의 학생에게 체육복을 빌릴 수 있음, 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수도 있음

 

set<int> l(lost.begin(), lost.end());
set<int> r(reserve.begin(), reserve.end());

// 중복 요소 제거
for(auto it=r.begin(); it!=r.end();) {
    if(l.find(*it) != l.end()) {
        l.erase(*it);
        it = r.erase(it);
    } else {
        it++;
    }
}

// erase로 iterator 값을 넘겨주면 삭제한 원소의 다음 원소를 가리키는 iterator를 반환함

// 이걸 이용해 set 중복 요소 제거 가능

    vector<int> vl(l.begin(), l.end());
    vector<int> vr(r.begin(), r.end());
    
    int ptr = 0, N = r.size();
    int answer = n;    
    for(int ll : vl) {
        while(ptr<N && vr[ptr]<ll-1) ptr++;
        if(ptr==N) {
            answer--;
            continue;
        }
        if(vr[ptr]==ll-1 || vr[ptr]==ll+1) {
            ptr++;
            continue;
        }
        answer--;
    }

// Greedy하게 도난당한 학생 중 제일 빠른 번호부터 여벌 가져온 학생에게 빌리도록 구현

int student[32];

int solution(int n, vector<int> lost, vector<int> reserve) {
    for(int l : lost) student[l]--;
    for(int r : reserve) student[r]++;
    
    int answer = n;
    for(int i=1; i<=n; i++) {
        if(student[i]==0) continue;
        if(student[i]==-1) {
            if(student[i-1]==1) {
                student[i-1] = student[i] = 0;
            } else if(student[i+1]==1) {
                student[i+1] = student[i] = 0;
            } else {
                answer--;
            }
        }
    }
    
    return answer;
}

// 이런 식으로 배열 만들어서 1,0,-1 로 상태 관리하는 게 훨씬 효율적이군요

 

조이스틱

- 좌우로 최소로 이동하면서 A가 아닌 모든 글자들 위치까지 가야 함

- 알파벳 이동은 필연적이므로 미리 횟수 구해두고, 좌우로 최대한 효율적으로 움직이는 방식으로 가야 함

    // 매 선택마다 가장 가까운 A가 아닌 수를 고르면 되겠구만
    int cur = 0; visited[0] = true;
    while(true) {
        int l = 1, r = 1;
        
        while(visited[(cur-l+N)%N] && l<N) l++;
        while(visited[(cur+r)%N] && r<N) r++;
        
        if(l>=N || r>=N) break;
        
        if(l<=r) {
            cur = (cur-l+N)%N;
            visited[cur] = true;
            answer += l;
        } else {
            cur = (cur+r)%N;
            visited[cur] = true;
            answer += r;
        }
    }

// 처음엔 greedy 방식으로 매 선택마다 가장 가까운 'A'가 아닌 근처 알파벳을 찾아가는 방식으로 구했으나,

// "ARAAACAAAAAAAAALA" 이런 예시의 경우 R->L->C 순서로 오른쪽 -> 왼쪽 -> 오른쪽 으로 가는 비효율 존재, 사실은 왼쪽 갔다가 오른쪽으로 꺾는 식이 최소 방식임

// 즉, 하나의 방향으로 쭉 가거나, 정방향으로 가다 역방향/역방향으로 가다 정방향 이렇게 한 번만 꺾는 선택을 해야 함

 

https://4z7l.github.io/2021/03/12/algorithms-prg-42860.html

[C++ 알고리즘] 프로그래머스 : 조이 스틱 - HERSTORY

int solution(string name) {
    int N = name.length();
    int answer = 0;
	for(int i=0; i<N; i++) {
        int h_move = name[i]-'A';
        answer += min(h_move, 26-h_move);
    }
    
    int vertical_move = N-1;
    for(int i=0; i<N; i++) {
        int j = i+1;
        while(j<N && name[j]=='A') j++;
        
        int left = i;
        int right = N-j; // 다음 'A'가 아닌 원소부터 끝까지의 거리
        
        vertical_move = min(vertical_move, min(left*2+right, left+right*2));
    }
    
    return answer+vertical_move;

 

큰 수 만들기

- 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자 구하기

string solution(string number, int k) {
    for(int i=0; i<k; i++) {
        int j = 1, N = number.length();
        while(j<N && number[j-1]>=number[j]) j++;
        number.erase(number.begin()+(j-1));
    }    
    return number;
}

// 다음 자리보다 작은 숫자를 삭제하면 좋음, 그리고 높은 자릿수를 삭제할수록 좋음

// 매번 1개씩 삭제할 때마다 최적의 선택을 하면 최종적으로 최적의 결과값이 나올 것(greedy)

// 얘는 O(k*N)의 시간 복잡도를 가지는데, 스택 이용하면 O(N) 가능하더라

string solution(string number, int k) {
    string answer = "";
    int pick = number.size() - k;
    
    for(char digit : number) {
        // 앞자리부터 스택에 넣음
        while(!answer.empty() && answer.back() < digit && k>0) {
            // 더 작은 값들은 pop, k번만큼
            answer.pop_back();
            k--;
        }
        answer.push_back(digit);
    }
    
    // 만약 삭제할 값들이 남았다면 (k>0 상태라면)
    answer.erase(answer.begin()+pick, answer.end());
    
    return answer;
}

// 스택 이용, 앞자리부터 스택에 push하며 이전 자리인데 본인보다 작은 숫자라면 pop 해버림

 

구명보트

- 몸무게 리스트가 주어지고, 구명보트 무게 제한이 주어질 때, 최대한 적은 보트로 모든 사람을 구출하고자 함

- 구명보트 탑승 인원이 2명으로 제한되어 쉬웠음

int solution(vector<int> people, int limit) {
    sort(people.begin(), people.end(), greater<int>());
    int answer = 0, N = people.size(), r = N;
    for(int l=0; l<N && l<r; l++) {
        if(people[l]+people[r-1]<=limit) r--;
        answer++;
    }
    
    return answer;
}

// 무게 높은 순으로 정렬 후, 한 명씩 자신의 pair를 찾는 식으로 고려하면 됨

 

섬 연결하기

- n개의 섬 사이에 다리 건설 비용(costs)이 주어질 때, 최소 비용으로 모든 섬이 서로 통행 가능하게 하는 방법

- MST(Minimum Spanning Tree) 문제

#include <vector>
#include <algorithm>
#define INT_MAX 2147483647

using namespace std;

vector<pair<int, int>> adj[100]; // 인접 리스트
vector<int> minCost(100, INT_MAX); // 각 노드까지의 최소 비용 (S에서 V-S로 가는 최소 비용)
vector<bool> added(100, false); // S 포함 여부 (MST에 추가되었는지 여부)

int solution(int n, vector<vector<int>> costs) {
    // 그래프 초기화
    for(auto cost : costs) {
        int u = cost[0], v = cost[1], e = cost[2];
        adj[u].push_back(make_pair(v,e));
        adj[v].push_back(make_pair(u,e));
    }
    
    // c 배열 초기화, 0번 vertex 선택
    added[0] = true; minCost[0] = 0;
    for(auto edge : adj[0]) {
        minCost[edge.first] = edge.second;
    }
    int answer = 0;
    
    for(int i=0; i<n-1; i++) {
        // MST에 추가할 최소 비용 정점 찾기
        int cur = 0, mc = INT_MAX;
        for(int j=1; j<n; j++) {
            if(!added[j] && (minCost[j]<mc)) {
                cur = j; mc = minCost[j];
            }
        }
        
        added[cur] = true;
        answer += minCost[cur];
        
        // 최소거리 업데이트
        for(auto edge : adj[cur]) {
            int next = edge.first, weight = edge.second;
            if(weight < minCost[next]) minCost[next] = weight;
        }
    }
    
    return answer;
}

// prim's algorithm 활용함

 

- kruskal algorithm을 활용해도 됨, different class인지는 union/find를 통해 parent 값이 같은지 확인하면 된

int parent[100];

bool comp(vector<int> a, vector<int> b) {
    // 길이 작은 순으로 edge 정렬
    return a[2] < b[2];
}
int getParent(int n) {
    if(parent[n]==n) return n;
    return parent[n] = getParent(parent[n]);
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0, nodes = 0;
    sort(costs.begin(), costs.end(), comp);
    
    for(int i=0; i<n; i++) parent[i] = i;
    
    for(auto cost : costs) {
        if(nodes >= n-1) break;
        
        int u = getParent(cost[0]);
        int v = getParent(cost[1]);
        int e = cost[2];
        
        if(u != v) { // 다른 클래스에 속해있으면
            parent[u] = v;
            answer += e;
            nodes++;
        }
    }
    
    return answer;
}

 

단속카메라

- 차량 진입/진출 지점이 배열로 주어짐, 카메라를 최소로 설치하여 모든 차량이 한 번은 단속용 카메라를 만나도록

- 진입 시간 기준 정렬하면 [0,10], [2,3], [4,5] 이런 경우에 문제가 됨!!

- 진출 시간 기준 정렬, 진출 지점에 카메라 설치하고/진입 지점 이후에 카메라 안만나면 해당 차량의 진출 지점에 또 설치

(greedy하게, 어차피 모든 차량은 한 번은 만나야되므로, 최대한 많이 겹치게 진출 지점에 카메라 만나도록!)

bool comp(vector<int> a, vector<int> b) {
    return a[1]<b[1];
}
int solution(vector<vector<int>> routes) {
    sort(routes.begin(), routes.end(), comp);
    
    int answer = 1, camera = routes[0][1];
    for(auto route : routes) {
        if(route[0] <= camera) continue;
        camera = route[1];
        answer++;
    }
    
    return answer;
}