프로그래머스(Lv 1) : 체육복
문제
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 전체 학생의 수는 2명 이상 30명 이하입니다.
- 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
- 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
풀이
전체 n명에서 만약 체육복을 못 빌려주면 -1 하는 방법으로 품.
체육복을 빌려주기에 앞서 자신의 체육복이 도둑맞으면 자기 자신을 먼저 챙기도록 짜야 하는게 이 문제의 핵심이다.
1) 체육복 유무에 따른 학생 배열 선언
2) lost 배열에 해당하면 -1, reserve 배열에 해당하면 +1
3) 만약 학생 배열에서 -1인 학생들에 대해 왼쪽, 오른쪽 학생의 여분에 따라 빌려줌
4) 빌려줄 수 있는 친구가 없으면 n--
코드
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = n; // 빌려줄 사람이 없으면 -1
int[] student = new int[n];
/* 1) 내껀 내가 입게 된다. */
for(int l : lost ) { student[l-1] -= 1; }
for( int r : reserve ) { student[r-1] += 1; }
/* 2) 체육복 빌려주기 */
for(int i=0; i<n; i++) {
if( student[i] == -1 ) { // 체육복이 없으면
if( i-1>=0 && student[i-1] == 1 ) { // 왼쪽 옆에 있는 친구가 빌려준다.
student[i] ++;
student[i-1] --;
} else if( i+1 < n && student[i+1] == 1 ) { // 오른쪽 옆에 있는 친구가 빌려준다.
student[i] ++;
student[i+1] --;
} else { // 빌려줄 사람이 없으면 이친구는 체육복을 못입는다.
answer--;
}
}
}
return answer;
}
}프로그래머스(Lv 2) : 큰 수 만들기
문제
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
풀이
기존 Sring에 담긴 배열에서 가장 큰 수를 Stack에 업데이트 해주었다.
코드
import java.util.Stack;
class Solution {
public String solution(String number, int k) {
char[] result = new char[number.length()-k];
Stack<Character> st = new Stack<>();
for (int i = 0; i < number.length(); i++) {
char c = number.charAt(i);
while( !st.isEmpty() && st.peek() < c && k-- > 0 ) {
st.pop();
}
st.push(c);
}
for (int i = 0; i < result.length; i++) {
result[i] = st.get(i);
}
return new String(result);
}
}프로그래머스(Lv 2) : 구명보트
문제
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
- 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.
풀이
최대 2명이라는 문제를 제대로 읽지 않아 삽질을 너무 많이 했다.
테스트케이스로 무게 제한 40kg 이상 240kg 이하로 두어야 풀린다.
풀이는 간단한데, 생각하는데 오래 걸렸다.
먼저 오름차순 정렬을 한다.
가장 작은 수와 가장 큰 수를 더 했을때, limit보다 작은 경우를 카운트해서 전체 사람 수에서 빼주면 된다는 걸 이해가 되면 된다.
코드
import java.util.Arrays;
class Solution {
public int solution(int[] people, int limit) {
int n = people.length;
Arrays.sort(people);
int i = 0, j = n-1;
for(; i<j; j-- ) {
if( people[i] + people[j] <= limit ) {
i++;
}
}
return n-i;
}
}프로그래머스(Lv 3) : 단속카메라
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.
제한사항
- 차량의 대수는 1대 이상 10,000대 이하입니다.
- routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
- 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
- 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.
풀이
Greedy로 접근하여 풀어야 한다.
백준 "회의실 배정" 문제풀 때와 비슷하게 풀 수 있다.
- 가장 최소 카메라 수는 1이므로 최초값을 1로 설정.
- 진출 지점을 기준으로 sort 할 수 있도록 class Route를 작성.
- 진출 지점을 기준으로 Route 정렬. (오름차순)
- 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난 것으로 간주한다는 문제의 설명에 따라, 진출 지점보다 진입 지점이 더 큰 경우에 기준 값을 변경하고 카메라 대수도 증가 시킴.
코드
class Solution {
static class Route {
int start;
int end;
public Route(int s, int e) {
this.start = s;
this.end = e;
}
}
static Comparator<Route> comp = new Comparator<Route>() {
@Override
public int compare(Route o1, Route o2) {
if( o1.end == o2.end )
return o1.start - o2.start;
else
return o1.end - o2.end;
}
};
public static int solution(int[][] routes) {
int answer = 1;
List<Route> list = new ArrayList<>();
for(int i=0; i<routes.length; i++) {
list.add(new Route(routes[i][0], routes[i][1]));
}
list.sort(comp);
Route now = list.get(0);
for( int i=1; i<list.size(); i++ ) {
if( now.end < list.get(i).start ) {
answer++;
now = list.get(i);
}
}
return answer;
}
}프로그래머스(Lv 3) : 저울
하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 합니다. 이 저울의 양팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같습니다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있습니다.
저울추가 담긴 배열 weight가 매개변수로 주어질 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 return 하도록 solution 함수를 작성해주세요.
예를 들어, 무게가 각각 [3, 1, 6, 2, 7, 30, 1]인 7개의 저울추를 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21입니다.
풀이
조합으로 가능한 무게를 모두 더해야 하는지 생각했는데, 너무 비효율적이라 생각이 들었다.
단순히 다른 방법이 있을 것이라 생각했고, 오름차순 정렬 후 누적합보다 큰 저울추가 있으면 누적합+1 값이 정답이 되도록 했다. 정답이 맞았는데, 왜 그런지 그 이유를 잘 모르겠다
- 저울추가 담긴 배열 오름차순 정렬
- sum(누적합)+1 보다 저울추가 크면 break;
코드
import java.util.Arrays;
class Solution {
public int solution(int[] weight) {
int answer = 0;
Arrays.sort(weight);
answer += weight[0];
for (int i = 1; i < weight.length; i++) {
if( answer+1 < weight[i] ) break;
answer += weight[i];
}
return answer+1;
}
}