[프로그래머스] 25 : 멀리 뛰기 | 귤 고르기

서예진·2024년 2월 19일
0

목차 💻

▸ 멀리 뛰기
▸ 귤 고르기


💡멀리 뛰기 : Lv.2

▼ 문제

출처: 프로그래머스 코딩테스트 연습 > 연습 문제 > 멀리 뛰기

▼ 내 풀이

  • 우선, 더해서 칸 수 n이 되는 숫자의 조합의 수를 구하려 했다.
  • 효진이는 1칸, 2칸 밖에 뛰지 못하기 때문에 조합은 1, 2로 이루어져 있다.
  • 문제를 풀기 위해 1칸 부터 5칸일 때의 반환해야할 수를 계산해보니 다음과 같았다.
칸 수result
11
22
33
45
58
  • 결과들을 보니 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;
    }
}
profile
안녕하세요

0개의 댓글