JUINTINATION
프로그래머스 코딩테스트 고득점 Kit - 탐욕법(체육복, 조이스틱, 큰 수 만들기, 구명보트, 섬 연결하기, 단속카메라) 본문
프로그래머스 코딩테스트 고득점 Kit - 탐욕법(체육복, 조이스틱, 큰 수 만들기, 구명보트, 섬 연결하기, 단속카메라)
DEOKJAE KWON 2024. 12. 24. 20:041번 문제: 체육복
https://school.programmers.co.kr/learn/courses/30/lessons/42862
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 하는데, 학생들은 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해야 한다.
접근
학생들이 가진 체육복의 수를 나타내는 정수 배열 arr를 만든다. 모두 기존에 1개의 체육복을 갖고 있었다는 가정하에 1을 채워넣은 뒤에 arr[lost 배열에 있는 인덱스]에 1을 빼고, arr[reserve 배열에 있는 인덱스]에 1을 더한다.
이후 학생들은 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있기 때문에 for문을 돌며 arr[i]가 0일 때(i번 학생이 체육복을 잃어버렸을 때) arr[i - 1] 또는 arr[i + 1]이 2라면(앞 또는 뒤 학생이 여분의 체육복을 갖고 있을 때) 값을 각각 더하고 뺀다.
만약 2가 아니라면 i번 학생은 체육수업을 들을 수 없기 때문에 전체 학생이 체육수업을 들을 수 있다는 가정하에 n부터 시작했던 answer에서 1을 빼고, 마지막에 반환한다.
코드
import java.util.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int[] arr = new int[n + 1];
Arrays.fill(arr, 1);
for (int l : lost) {
arr[l]--;
}
for (int r : reserve) {
arr[r]++;
}
int answer = n;
for (int i = 1; i <= n; i++) {
if (arr[i] == 0) {
if (arr[i - 1] == 2) {
arr[i - 1]--;
arr[i]++;
} else if (i + 1 <= n && arr[i + 1] == 2) {
arr[i + 1]--;
arr[i]++;
} else {
answer--;
}
}
}
return answer;
}
}2번 문제: 조이스틱
https://school.programmers.co.kr/learn/courses/30/lessons/42860
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
조이스틱을 각 방향으로 움직이면 아래와 같다.
▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)조이스틱으로 알파벳 이름을 완성해야할 때 맨 처음엔 A로만 이루어져 있다. 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA로 시작한다. 예를 들어 아래의 방법으로 "JAZ"를 만들 수 있다.
- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동이다.만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만들어야 한다.
접근
▲ 또는 ▼로 알파벳을 맞추는 최소 조작 횟수는 해당 알파벳이 A와 가까운지, Z와 가까운지 확인해야 한다. 이를 위해 현재 위치 i에 있는 알파벳을 c라고 할 때 for문에서 Math.min(c - 'A', 'Z' - c + 1)을 진행하고, 위 아래 조작 횟수를 의미하는 upDownMove에 더한다.
이후 ◀ 또는 ▶로 커서를 양옆으로 이동하는 최소 조작 횟수를 구해야 한다. while문을 통해 c의 오른쪽에서 처음 나타나는 A가 아닌 다른 알파벳의 위치인 next를 구한다. 이를 구하는 이유는 "AAAAB"처럼 오른쪽으로 계속 이동하는 것보다 맨 처음 위치에서 왼쪽으로 한 번 이동하는 것이 더 효율적일 수 있기 때문이다. next는 아래와 같이 사용된다.
현재 위치인 i까지 맨 처음 위치인 0부터 오른쪽으로 이동하는 조작 횟수 i와 문자열의 길이 n - next 중 더 작은 수를 구한다. 이는 맨 처음 위치에서 현재 위치 i까지 오른쪽으로 먼저 이동할 것인지, 아니면 next까지 왼쪽으로 먼저 이동한 뒤 진행할 것인지 구하는 것이다. 이렇게 구한 수에 맨 처음 위치부터 현재 위치 i까지 오른쪽으로 이동한 횟수와 맨 처음 위치부터 next까지 왼쪽으로 이동한 횟수를 더한다.
이렇게 만들어진 수는 for문 안에서 초기값이 오른쪽으로만 이동하는 횟수인 n - 1로 시작하는 leftRightMove 변수와 비교하며 가장 작은 수를 찾는다. 마지막에 upDownMove와 leftRightMove를 더한 값을 반환한다.
코드
class Solution {
public int solution(String name) {
int n = name.length();
int upDownMove = 0, leftRightMove = n - 1;
for (int i = 0; i < n; i++) {
char c = name.charAt(i);
upDownMove += Math.min(c - 'A', 'Z' - c + 1);
int next = i + 1;
while (next < n && name.charAt(next) == 'A') {
next++;
}
leftRightMove = Math.min(leftRightMove, Math.min(i, n - next) + i + n - next);
}
return upDownMove + leftRightMove;
}
}3번 문제: 큰 수 만들기
https://school.programmers.co.kr/learn/courses/30/lessons/42883
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 한다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있으며, 이 중 가장 큰 숫자는 94이다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어질 때 number에서 k 개의 수를 제거하여 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성해야 한다.
접근
반환해야 할 숫자(문자열)의 길이는 number의 길이 n에서 k만큼을 빼준 길이가 된다. 따라서 for문에서 i는 0부터 n - k - 1까지 순회한다. 해당 for문 안의 for문의 범위는 j가 0부터 시작하는 탐색할 인덱스(idx)부터 결국 문자열의 끝까지 탐색해야 하므로 i + k까지 순회한다.
number 문자열의 j번째 문자를 c라고 할 때 idx ~ i + k까지 비교했을 때 가장 큰 수 max를 찾고, 그 다음 인덱스부터 가장 큰 수를 찾아야하기 때문에 idx를 j + 1로 초기화한다.
예시 중 하나인 number = " 4177252841", k = 4을 기준으로 보면 다음과 같다.
- 첫번째 자리
- (41772) 52841
- 두번째 자리
- (
17725) 2841
- (
- 세번째 자리
- (
77252) 841
- (
- 네번째 자리
- (
72528) 41
- (
- 다섯번째 자리
- (
25284) 1
- (
- 여섯번째 자리
- (
52841)
- (
이렇게 구한 max값들을 StringBuilder sb에 하나씩 붙이다가 마지막에 문자열 타입으로 바꿔서 반환하면 된다.
코드
class Solution {
public String solution(String number, int k) {
int n = number.length(), idx = 0;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n - k; i++) {
char max = '0';
for (int j = idx; j <= i + k; j++) {
char c = number.charAt(j);
if (max < c) {
max = c;
idx = j + 1;
}
}
sb.append(max);
}
return sb.toString();
}
}4번 문제: 구명보트
https://school.programmers.co.kr/learn/courses/30/lessons/42885
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 할 때 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만, 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 할 때 주어진 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit에서 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해야 한다.
접근
가벼운 사람과 무거운 사람들을 순서대로 뺄 수 있도록 Deque를 사용한다. people 배열을 오름차순으로 정렬하고 선언한 덱에 순서대로 집어넣는다.
이후 덱이 빌 때까지 남아있는 사람 중 가장 무거운 사람(덱의 맨 뒤에 있는 값)을 poll한 뒤 남아있는 사람 중 가장 가까운 사람(덱의 맨 앞에 있는 값)을 peek한 값의 무게의 합과 limit을 비교한다.
limit보다 값이 작거나 같다면 보트에 탈 수 있으므로 deque.pollFirst를 진행하고, limit보다 크다면 넘어간다. 이 과정을 진행할 때마다 answer에 1을 더해주며, 마지막에 이를 반환한다.
코드
import java.util.*;
class Solution {
public int solution(int[] people, int limit) {
Deque<Integer> deque = new ArrayDeque<>();
Arrays.sort(people);
for (int person : people) {
deque.addLast(person);
}
int answer = 0;
while (!deque.isEmpty()) {
int last = deque.pollLast();
if (!deque.isEmpty() && last + deque.peekFirst() <= limit) {
deque.pollFirst();
}
answer++;
}
return answer;
}
}5번 문제: 섬 연결하기
https://school.programmers.co.kr/learn/courses/30/lessons/42861
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성해야 한다.
이때 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 본다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능하다.
접근
대놓고 MST를 사용해서 해결하라는 문제이다. 이전에 작성했던 최소 신장 트리(Minimum Spanning Tree) 글을 참고했으며, 크루스칼 알고리즘과 프림 알고리즘 중 크루스칼 알고리즘을 사용했다.
Point 클래스는 위의 글에서 Node 클래스와 동일한 역할을 하며, Point.from 정점에서 Point.to 정점으로 가는 간선의 가중치가 Point.cost이다. 이후 우선순위 큐에서 cost를 기준으로 꺼낼 것이기 때문에 Comparable<Point>를 implements하고, compareTo(T o) 메서드를 오버라이딩했다.
어떤 섬과 연결된 부모섬의 번호를 저장하는 parent 배열을 makeSet 메서드로 초기화하고, List<Point> points를 선언하여 costs 배열의 모든 값을 Point 타입으로 저장한다.
마지막에 getKruskalMST 메서드를 활용하여 모든 섬이 서로 통행 가능하도록 만드는 최소 비용을 반환하는데, 먼저 PriorityQueue<Point> pQueue를 선언하고, list에 있는 모든 Point 값들을 삽입한다. 이후 0부터 시작하는, 간선 edge의 수를 의미하는 numOfEdges가 n - 1이 될 때까지 while문을 반복한다. 해당 while문 안에서는 pQueue에서 가장 작은 p.cost 값을 가지는 Point 타입의 p를 poll하고, p의 from과 to가 연결돼있는지 isUnion 메서드를 통해 확인한다.
연결돼있지 않은 경우 연결한 뒤 cost의 합을 의미하는, 0부터 시작하는 sum에 p.cost를 더해주고, 마지막에 sum을 반환한다.
코드
import java.util.*;
class Point implements Comparable<Point> {
private int from, to, cost;
public Point(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
public int getFrom() {
return from;
}
public int getTo() {
return to;
}
public int getCost() {
return cost;
}
@Override
public int compareTo(Point o) {
return this.cost - o.cost;
}
}
class Solution {
public int getKruskalMST(List<Point> points, int[] parent, int n) {
PriorityQueue<Point> pQueue = new PriorityQueue<>();
for (Point point : points) {
pQueue.offer(point);
}
int sum = 0, numOfEdges = 0;
while (numOfEdges < n - 1) {
Point p = pQueue.poll();
if (!isUnion(parent, p.getFrom(), p.getTo())) {
unionSet(parent, p.getFrom(), p.getTo());
numOfEdges++;
sum += p.getCost();
}
}
return sum;
}
public void makeSet(int[] parent, int x) {
parent[x] = x;
}
public int findSet(int[] parent, int x) {
if (parent[x] == x) return x;
return parent[x] = findSet(parent, parent[x]);
}
public void unionSet(int[] parent, int a, int b) {
a = findSet(parent, a);
b = findSet(parent, b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
public boolean isUnion(int[] parent, int a, int b) {
a = findSet(parent, a);
b = findSet(parent, b);
return a == b;
}
public int solution(int n, int[][] costs) {
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
makeSet(parent, i);
}
List<Point> points = new ArrayList<>();
for (int[] c : costs) {
int from = c[0], to = c[1], cost = c[2];
points.add(new Point(from, to, cost));
}
return getKruskalMST(points, parent, n);
}
}6번 문제: 단속카메라
https://school.programmers.co.kr/learn/courses/30/lessons/42884
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 한다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성해야 한다.
접근
문제의 나온 예시를 그림으로 그리면 아래와 같다.
먼저 routes를 Arrays.sort를 사용하여 차량의 진출 지점을 기준으로 오름차순으로 정렬한다. 정렬한 이후의 예시를 그림으로 그리면 아래와 같다.
그림에서 빨간색 선(진출 지점)을 기준으로 정렬한 것이다.
설치할 카메라의 위치를 의미하는 camera는 Integer.MIN_VALUE부터 시작하는데, 문제의 제한사항을 보면 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하이기 때문에 -30000부터 시작해도 되긴 한다.
아무튼 모든 차량이 한 번은 단속용 카메라를 만나기만 하면 되기 때문에 카메라는 차량의 이동 경로가 겹치는 부분에 설치하면 될 것이다. 현재 카메라가 i번째 차량(routes[i])의 이동 경로(route)의 진입 지점보다 앞에 있다면(camera < route[0]) 카메라를 해당 차량의 진출 지점에 설치(camera = route[1])하고 카메라의 개수를 의미하는 answer에 1을 더하는 과정을 반복하고, 마지막에 이를 반환하면 된다. 예시의 결과를 그림으로 그리면 아래와 같다.
cam1은 처음 카메라의 위치인 Integer.MIN_VALUE보다 2번 차량의 진입 지점(-18)이 뒤에 있기 때문에 2번 차량의 진출 지점(-13)에 설치한다. 1번 차량의 진입 지점(-14)은 cam1의 위치보다 앞에 있기 때문에 해당 카메라를 지나간다.
이때 1번 차량의 진출 지점은 신경쓰지 않아도 되는 이유는 진출 지점을 기준으로 오름차순 정렬을 진행했기 때문이다. 앞에서 이미 cam1은 1번 차량보다 진출 지점이 같거나 앞에 있는 2번 차량의 진출 지점에 설치됐기 때문에 해당 카메라를 무조건 지나가게 되어있다.
3번 차량의 진입 지점(-5)은 cam1의 위치보다 뒤에 있기 때문에 cam1을 지나가지 않는다. 따라서 cam2를 3번 차량의 진출 지점(-3)에 설치한다.
마지막 0번 차량의 진입 지점(-20)은 cam2의 위치보다 앞에 있기 때문에 해당 카메라를 지나가며, 이와 같이 최소 2개의 카메라만 설치하면 모든 차량이 단속 카메라를 한 번 이상 지나가게 된다.
코드
import java.util.*;
class Solution {
public int solution(int[][] routes) {
Arrays.sort(routes, (o1, o2) -> o1[1] - o2[1]);
int answer = 0;
int camera = Integer.MIN_VALUE;
for (int[] route : routes) {
if (camera < route[0]) {
camera = route[1];
answer++;
}
}
return answer;
}
}결론
그리디 알고리즘은 내가 제일 약한 파트 중 하나이다. 사고방식을 거꾸로 해야 한다는데 아직 너무 어렵다. 그래서 알고리즘을 생각하기까지 시간이 너무 오래 걸리고, 이에 따라 코드를 작성하기까지의 시간 또한 오래 걸리게 된다.
작성했다고 해도 설명하기가 너무 어려운데, 특히 조이스틱과 큰 수 만들기 문제가 오래 걸렸다. 구명보트처럼 너무 쉬운 문제가 있고, 위의 문제들처럼 너무 어려운 문제가 있듯이 난이도가 천차만별인 알고리즘 문제들의 집합체여서 힘들었다.
번아웃이 와서 이틀 정도 아무것도 안 하고 쉬었는데, 잘 쉬었으니 이제 다시 달려가보자.. 화이팅!