프로그래머스 고득점 Kit 하루만에 뽀개기 - 6. 그리디(Java, C++) 풀이

https://programmers.co.kr/learn/courses/30/parts/12244

프로그래머스

- 알고리즘 풀이로 C++를 주로 사용하다가 기업 코딩테스트를 위해 java 풀이를 학습하는 사람에게 도움이 될만한 포스트입니다. 알고리즘 적인 해설내용은 줄이고 C++에 익숙한 사람들이 Java 사용시 놓칠만한 내용 위주로 작성하고 있습니다.

- 그리디 같은 경우는 별다른 자료구조나 알고리즘이 필요없다. 다만 배열 조작을 위한 메서드들은 미리 공부해놓을 필요가 있다. 

 

1. 체육복

https://programmers.co.kr/learn/courses/30/lessons/42862 

코딩테스트 연습 - 체육복

- 학생별 체육복 갯수를 셋팅해놓고, 학생 앞뒤로 체육복 여벌이 있으면 1개 넘겨준다

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int ans = 0;
        int[] arr = new int[n];
        Arrays.fill(arr, 1);
        for(int i: lost) --arr[i-1];
        for(int i: reserve) ++arr[i-1];
        
        for(int i = 0; i < n; ++i) {
            if(i-1 >= 0 && arr[i] > 1 && arr[i-1] == 0) {
                ++arr[i-1];
                --arr[i];
            }
            if(i+1 < n && arr[i] > 1 && arr[i+1] == 0) {
                ++arr[i+1];
                --arr[i];
            }
        }
        
        for(int i: arr) {
            if(i > 0) ++ans;
        }
        return ans;
    }
}

- Arrays.fill

 

2. 조이스틱

https://programmers.co.kr/learn/courses/30/lessons/42860

코딩테스트 연습 - 조이스틱

- 조이스틱 상하 조작에 대한 횟수, 좌우 연산에 대한 횟수를 따로 구한다
- 상하 횟수는 A에서 name[i]까지의 이동횟수이다
- 커서 위치 시작은 0이고, 따라서 기존 방문한 곳을 다시 방문하지 않는 좌우 연산의 최대값은 0에서 오른쪽으로 끝까지 가는 것이다.
- A는 따로 상하조작을 하지 않아도 되서 방문하지 않아도 된다., 오른쪽으로 갔다가 다시 왼쪽으로 가서 A 직전까지 갔다가 다시 되돌아 가는 경우를 생각할 수 있다.  오른쪽,왼쪽 혹은 왼쪽,오른쪽으로 갔다가 마지막으로 A가 아닌 자리로 까지 가는 데 필요한 횟수를 계속 구해나가면서 최소값을 찾는다. 

import java.util.*;

class Solution {
    public int solution(String name) {
        int ans = 0, N = name.length();
        
        for(int i = 0; i < N; ++i) {
            ans += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);
        }
        
        int mv = N - 1, pos = 0;
        for(int i = 0; i < N; ++i) {
            pos = i + 1;
            while(pos < N && name.charAt(pos) == 'A') ++pos;
            mv = Math.min(mv, i + (N - pos) + Math.min(i, N - pos));
        }
        
        return ans + mv;
    }
}

 

 

3. 큰 수 만들기

https://programmers.co.kr/learn/courses/30/lessons/42883 

코딩테스트 연습 - 큰 수 만들기

- numbers에서 앞에서 부터 가장 큰 char값을 찾아서 계속 ans에 더해 준다. 가장큰 char의 idx를 계속 기록하고, 그 지점 다음 부터 큰 값을 계속 찾아 나가므로 이중 for문이지만 그리디한 접근법이다. 

// C++
#include <string>
#include <vector>
using namespace std;

string solution(string number, int k) {
    string ans;
    int N = number.length();
    
    for(int i = 0, p = -1; i < N - k; ++i) {
        char ch = '0';
        for(int j = p + 1; j <= i + k; ++j) {
            if(ch < number[j]) {
                ch = number[j];
                p = j;
            }
        }
        ans += ch;
    }
    return ans;
}

 

4. 구명보트

https://programmers.co.kr/learn/courses/30/lessons/42885?language=java 

코딩테스트 연습 - 구명보트

- 이분탐색 방식과 유사하게 풀었다. 보트가 한번에 2명씩 탈 수 있으므로, 최대+최소무게 사람이 탈 수 있으면 둘 다 탈 수 있고 그렇지 않으면 최대무게 사람만 보트를 탈 수 있다. 

// java
import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0, N = people.length;
        Arrays.sort(people);
        
        int s = 0, e = N - 1;
        while(s <= e) {
            if(people[s] + people[e] <= limit) ++s;
            --e, ++answer;
        }
        return answer;
    }
}

 

5. 섬 연결하기

https://programmers.co.kr/learn/courses/30/lessons/42861 

코딩테스트 연습 - 섬 연결하기

- 섬을 모두 연결하는데 최소의 비용으로 연결해야 한다. 이는 곧 MST 최소스패닝트리를 찾는 것 이다. 
- 노드 집합 간에 disjoint set 상호배타적 집합인지를 판별하는 union-find 연산을 이용하는 O(ElogE) 복잡도의 크루스칼 알고리즘을 사용해서 MST를 구할 수 있다. 간선 중에 음수값이 있으면 O(V^2) 복잡도의 프림 알고리즘을 사용해야 한다.
- 주어진 edge들을 비용에 대해서 정렬한 다음, 가장 저렴한 비용의 간선부터 차례대로 세어나가면서 만약 이 간선을 이용할 두 노드가 상호배타적 집합인지 아닌지를 체크해서 만약 아니면 p 배열로 구현한 부모값을 일치시켜주고 이 간선을 사용한다(전체 비용에 더해준다)

// C++
#include <vector>
#include <algorithm>
using namespace std;

int p[101];

int Find(int x) {
    if(x == p[x]) return x;
    else {
        int y = Find(p[x]);
        p[x] = y;
        return y;
    }
}

int solution(int n, vector<vector<int>> costs) { // u, v, w
    sort(costs.begin(), costs.end(), [](vector<int> a, vector<int> b) {
        return a[2] < b[2]; 
    });
    for(int i = 1; i <= n; ++i) {
        p[i] = i;
    }
    
    int ans = 0;
    for(int i = 0; i < costs.size(); ++i) {
        int u = costs[i][0], v = costs[i][1], w = costs[i][2];
        u = Find(u), v = Find(v);
        if(u != v) {
            p[u] = v;
            ans += w;
        }
    }
    return ans;
}

import java.util.*;

// java
class Solution {
    int[] p = new int[101];
    
    public int solution(int n, int[][] costs) { // u, v, w
        Arrays.sort(costs, (a, b) -> a[2] - b[2]);
        for(int i = 1; i <= n; ++i) {
            p[i] = i;
        }
        
        int ans = 0;
        for(int i = 0; i < costs.length; ++i) {
            int u = costs[i][0], v = costs[i][1], w = costs[i][2];
            u = Find(u);
            v = Find(v);
            if(u != v) {
                p[u] = v;
                ans += w;
            }
        }
        
        return ans;
    }
    
    int Find(int x) {
        if(x == p[x]) return x;
        else {
            int y = Find(p[x]);
            p[x] = y;
            return y;
        }
    }
}

 

6. 단속카메라

- 모든 차량이동 경로에 대해서 시작점으로 정렬한 뒤에 앞 차량이 나간 지점보다 뒷 차량이 들어온 지점이 서로 떨어져있으면 새로운 카메라 설치지점이 필요한 것이다. 

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        Arrays.sort(routes, (a, b) -> a[0] - b[0]);
        
        int ans = 1, out = routes[0][1];
        for(int[] p: routes) {
            int s = p[0], e = p[1];
            if(out < s) {
                ++ans;
                out = e;
            }
            if(out > e) out = e;
        }
        
        return ans;
    }
}