프로그래머스LV2_5

점프와 순간 이동

접근 과정

1. N부터 시작하여 N이 0이 될 때까지 반복하여 K를 반환
2. N이 짝수라면 순간 이동하면 되므로 N을 반으로 만든다.
3. N이 홀수라면 무조건 한 칸 이동해야 되므로 K를 1늘리고 N을 1뺀다.

시행착오

• dp 방식으로 풀었는데 효율성에서 메모리 초과와 시간 초과를 겪었다.(제한 사항에 N이 10억이라서 너무 크다.)
  

    import java.util.*;
    
    public class Solution {
        public int solution(int n) {
            while(n % 2 == 0){
                n /= 2;
            }
            int[] dp = new int[n + 1];
            dp[0] = 0;
            dp[1] = 1;
            for(int i = 2; i <= n; i++){
                if(i % 2 == 0) dp[i] = Math.min(dp[i - 1] + 1, dp[i / 2]);
                else dp[i] = dp[i - 1] + 1;
            }
            return dp[n];
        }
    }

해결 코드

• dp 방식으로 풀면 제한 사항에 N이 10억까지랑 메모리 초과가 날 수 있다. 따라서 N부터 시작해 짝수, 음수에 따라 줄이는 방식으로 계산하면 해결된다.
• 다른 사람 풀이를 봤는데 이 문제는 결국 N을 2진수로 바꿨을 때 1의 개수를 말하는 것이라서 한 줄이면 해결되는 문제였다!
  

    import java.util.*;
    
    public class Solution {
        public int solution(int n) {
            int K = 0;
            while(n != 0){
                if(n % 2 == 0) n /= 2;
                else{
                    K++;
                    n--;
                }
            }
            return K;
        }
    }
    
    // 개선
    public class Solution {
        public int solution(int n) {
            return Integer.bitCount(n);
        }
    }

시간복잡도

귤 고르기

접근 과정

1. 귤을 크기 순으로 정렬
2. 개수를 세기 위해 가장 큰 귤의 크기만큼 배열을 만듦
3. 귤 배열을 돌면서 각 귤 크기의 개수를 셈
4. 귤 개수가 많은 것부터 상자에 담아 answer를 1씩 늘리면서 k보다 크거나 같아지면 그만 넣고 answer를 반환하여 해결

시행착오

• 시행착오 없이 접근 과정대로 구현하여 해결

해결 코드

• 문제를 해결하고 나서 이것도 공간복잡도가 너무 크다고 생각하여 다른 사람 풀이를 참고하니 해시맵을 활용하여 해결할 수 있어 개선해보았다.
  

    import java.util.*;
    
    class Solution {
        public int solution(int k, int[] tangerine) {
            int answer = 0;
            Arrays.sort(tangerine);
            int[] cnt = new int[tangerine[tangerine.length - 1] + 1];
            for(int i = 0; i < tangerine.length; i++){
                cnt[tangerine[i]]++;
            }
            Arrays.sort(cnt);
            int cur = 0;
            for(int i = cnt.length - 1; i >= 0; i--){
                cur += cnt[i];
                answer++;
                if(cur >= k) break;
            }
            return answer;
        }
    }
    
    // 개선->O(N)
    import java.util.*;
    
    class Solution {
        public int solution(int k, int[] tangerine) {
            int answer = 0;
            Map<Integer, Integer> m = new HashMap<>();
            for(int t : tangerine){
                m.put(t, m.getOrDefault(t, 0) + 1);
            }
            List<Integer> cnt = new ArrayList<>(m.values());
            cnt.sort(Collections.reverseOrder());
            int cur = 0;
            for(int c : cnt){
                cur += c;
                answer++;
                if(cur >= k) break;
            }
            return answer;
        }
    }

시간복잡도