[코딩테스트] 23-11-29 프로그래머스

 

1.

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

class Solution {
    public int solution(int n) {
        final int MOD = 1234567;
        int[] dp = new int[n + 1];

        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        }

        return dp[n];
    }
}

이는 동적 계획법을 적용하면 됩니다. 1,2칸씩 뛸 수 있다고 하니 dp[i] = dp[i-1]+dp[i-2] 가 됩니다. 거기에 문제에 1234567을 나누고 난 나머지를 쓰라고 했으니 % 1234567을 해주면 됩니다.

2.

https://school.programmers.co.kr/learn/courses/30/lessons/138476

프로그래머스

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        Map<Integer, Integer> countMap = new HashMap<>();

        for (int size : tangerine) {
            countMap.put(size, countMap.getOrDefault(size, 0) + 1);
        }

        List<Map.Entry<Integer, Integer>> sortedList = new ArrayList<>(countMap.entrySet());
        sortedList.sort(Map.Entry.comparingByValue(Comparator.reverseOrder()));

        int count = 0;

        for (Map.Entry<Integer, Integer> entry : sortedList) {
            int value = entry.getValue();
            int maxUse = Math.min(k, value);

            k -= maxUse;
            count += 1;

            if (k <= 0) {
                break;
            }
        }

        return count;
    }
}

Value 값에 따라 정렬 하고 조회하는 문제가 많이 나오는 것 같습니다. 잘 외워두면 유용하겠죠?
간단히 순서로 나타내면
1. List에 Map을 넣고 value의 크기에 따라 역순(내림차순)으로 정렬
2. List의 제네릭인 Map.Entry<Integer, Integer>를 이용하여 향상된 for문을 실행
3. value값을 기준으로 내림차순으로 정렬 되어 있으니 그에 따라 key값도 정렬되어 있습니다.
4. value값 기준으로 key값과 value값 호출하여 니즈에 맞게 이용합니다.

3.

https://school.programmers.co.kr/learn/courses/30/lessons/131701

프로그래머스

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        int length = elements.length;
        Set<Integer> sumSet = new HashSet<>();

        for (int i = 0; i < length; i++) {
            int sum = 0;
            for (int j = i; j < i + length; j++) {
                sum += elements[j % length];
                sumSet.add(sum);
            }
        }

        return sumSet.size();
    }
}

원래는 갯수를 기준으로 1개씩 더할 때, 2개씩 더할 때, ... 로 코딩을 했었습니다. 그런데 그렇게 했더니 너무 코드가 지저분 해지고 알아보기 힘들어지기에 생각을 바꿔서 덧셈 시작 위치를 기준으로 계산을 했습니다. 0번 인덱스에서 1개 ~ elements.length 개까지 더하면서 sumSet.add을 반복 했더니 훨씬 깔끔하고 직관적인 코드가 나올 수 있게 됐습니다.

4.

https://school.programmers.co.kr/learn/courses/30/lessons/76502

프로그래머스

class Solution {
    public int solution(String s) {
        int answer = 0;
        
        for(int i = 0; i < s.length(); i++){
            if(removeParenthesis(s, s.length()).length() == 0) answer++;
            
            String firstString = Character.toString(s.charAt(0));
            s = s.substring(1);
            s += firstString;
        }
        
        return answer;
    }
    
    public String removeParenthesis(String parenthesis, int length){
        String[] pts = {"{}", "[]", "()"};
        
        for(int i = 0; i < length/2; i++){
            for(int j = 0; j < 3; j++){
                parenthesis = parenthesis.replace(pts[j], "");
            }
        }
        
        return parenthesis;
    }
}

s에서 괄호들을 지운 뒤, 길이를 재는 방식으로 풀어보았습니다.
계산을 해보니 (s의 길이)/2만큼 순차적으로 지우면 돼서 removeParenthesis를 위와 같이 코딩했습니다. (혹시 더 효율적으로 지우는 방법이 있나요?) "지우고 체크하고 순서 바꾸고"를 반복하며 길이가 0이 되는 경우의 수를 셌습니다.

5.

https://school.programmers.co.kr/learn/courses/30/lessons/131127

프로그래머스

import java.util.*;

class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
        int answer = 0;

        for (int i = 0; i <= discount.length - 10; i++) {
            Map<String, Integer> memo = new HashMap<>();
            for (int j = 0; j < want.length; j++) {
                memo.put(want[j], number[j]);
            }

            boolean valid = true;
            for (int k = i; k < i + 10; k++) {
                if (memo.containsKey(discount[k]) && memo.get(discount[k]) > 0) {
                    memo.put(discount[k], memo.get(discount[k]) - 1);
                } else {
                    valid = false;
                    break;
                }
            }

            if (valid) {
                answer++;
            }
        }

        return answer;
    }
}

number의 원소의 합은 10이라고 했으니 무조건 다 살 수 있으려면 discount의 항목에서 want에 없는 항목이 나와서는 안 됩니다. 그러니 memo의 key에 discount[k]가 있어야 하며 0개가 넘어야 합니다.
그 조건을 만족하지 못하면 결국 memo의 value의 총 합은 0이 될 수 없으니 false를 반환 해주고 true가 될 때는 answer를 증가 시켜주도록 합니다.