목차 💻
▸ 멀리 뛰기
▸ 귤 고르기
💡멀리 뛰기 : Lv.2
▼ 문제
출처: 프로그래머스 코딩테스트 연습 > 연습 문제 > 멀리 뛰기
▼ 내 풀이
- 우선, 더해서 칸 수 n이 되는 숫자의 조합의 수를 구하려 했다.
- 효진이는 1칸, 2칸 밖에 뛰지 못하기 때문에 조합은 1, 2로 이루어져 있다.
- 문제를 풀기 위해 1칸 부터 5칸일 때의 반환해야할 수를 계산해보니 다음과 같았다.
| 칸 수 | result |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
| 5 | 8 |
- 결과들을 보니 5번째 칸 수는 3, 4칸 수의 결과값을 더한 것과 같은 것을 알 수 있었다.
- 따라서 피보나치 수 풀이를 참고해서 문제를 풀었다.
- 또한, n이 1인 경우와 2인 경우를 먼저 처리한 후 위에서 생각한 풀이 과정을 구현했다.
class Solution {
public long solution(int n) {
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
long[] arr = new long[n+1];
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;
for(int i = 3; i <= n; i++){
arr[i] = (arr[i-1] + arr[i-2])%1234567;
}
return arr[n];
}
}▼ 알게된 점
- 피보나치 수 문제와 이 문제의 풀이가 공통된다는 것을 알고 검색해보니 이와 같은 문제 풀이를 동적 프로그래밍(DP)이라고 한다.
Dynamic Programming
- 큰 문제를 작은 문제로 나누어 푸는 문제를 가리킨다.
- Dynamic Programming의 조건:
1. 작은 문제가 반복이 일어나는 경우
2. 같은 문제를 구할 때마다 정답이 같은 경우
- 위의 사진 처럼 큰 문제가 작은 문제로 나누어진 경우 이 풀이를 적용할 수 있다.
- 멀리 뛰기 문제에서도 DP를 적용할 수 있는 이유를 설명하자면 다음과 같다.
<칸 수 = 2>
1+1
2
<칸 수 = 3>
1+1+1
1+2
2+1
이때, 칸 수 = 4인 경우를 보면,
1+1+1+1
1+2+1
2+1+1 -> 칸 수 = 3인 경우에서 +1
1+1+2
2+2 -> 칸 수 = 2인 경우에서 +2
따라서 칸 수 = 4인 경우는 칸 수 = 2와 3인 경우의 결과값을 더하며 된다.
💡귤 고르기 : Lv.2
▼ 문제
출처: 프로그래머스 코딩테스트 연습 > 연습 문제 > 귤 고르기
▼ 내 풀이
- 문제에서 서로 다른 크기의 수를 최소화하기 위해 귤의 수가 많은 크기의 귤을 가져오는 방식으로 접근했다.
- 먼저, 크기 별 귤의 수를 Map을 사용하여 저장했다.
- 이후, value들을 리스트에 담아 내림차순으로 정렬했다.
- for문을 활용하여 리스트를 돌면서 sum에 귤의 수를 저장하고 cnt++한다. 이때 sum에 귤의 수를 더했을 때 k를 넘는다면 cnt++하고 break한다.
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class Solution {
public int solution(int k, int[] tangerine) {
Map<Integer, Integer> map = new HashMap<>();
//map에 저장
for(int t : tangerine){
map.put(t, map.getOrDefault(t, 0) + 1);
}
//리스트에 저장 및 정렬
List<Integer> values = new ArrayList<>(map.values());
Collections.sort(values, Collections.reverseOrder());
//귤 담기
int sum = 0; //귤의 수
int cnt = 0; //최솟값
for(int n : values){
if(sum + n >= k){
cnt++;
break;
} else{
sum += n;
cnt++;
}
}
return cnt;
}
}
안녕하세요