프로그래머스(단어 변환, 예산) - Java

[단어 변환]

https://programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

 

* 조건

1. 시작 단어(begin), 만들고자 하는 단어(target), 단어 리스트(words)가 주어진다
2. begin에서 시작해서 words의 단어들을 가지고 target을 만들 수 있는 단계를 구한다
3. 한 번에 한 개의 알파벳만 바꿀 수 있다
4. words에 있는 단어로만 변환 가능하다
5. 변환할 수 없다면 0을 출력한다

* 알고리즘

• DFS 또는 BFS

 

* 로직(Logic)

• begin과 한 글자 차이나는 단어를 찾게되면 재귀를 수행한다
• 만약 target과 같아지면 최소 단계로 계속 덮어준다

 

public class Problem_ConvertWord {

    static boolean[] checked;
    static int N;
    static String[] Words;
    static int result = Integer.MAX_VALUE;

    public static void main(String[] args) {
        String begin = "hit";
        String target = "cog";
        String[] words = {
                "hot", "dot", "dog", "lot", "log", "cog"
        };

        int answer = solution(begin, target, words);
        System.out.println(answer);
    }

    public static int solution(String begin, String target, String[] words) {
        int answer = 0;
        N = words.length;
        Words = words.clone();
        checked = new boolean[N];

        int count = 0;
        doDfs(begin, target, count);

        answer = result == Integer.MAX_VALUE ? 0 : result;
        return answer;
    }

    private static void doDfs(String begin, String target, int count) {
        if(count > result) return;
        if(begin.equals(target)){
            result = Math.min(result, count);
        }

        for(int i=0; i<N; ++i){
            if(!checked[i]){
                //글자수가 한개 차이인지 확인
                if(findAdjWord(begin, i)){
                    checked[i] = true;
                    doDfs(Words[i], target, count+1);
                    checked[i] = false;
                }
            }
        }
    }

    private static boolean findAdjWord(String begin, int adjNode) {
        int cnt=0;
        for(int s=0; s<begin.length(); ++s){
            String tmp = begin.substring(s, s+1);
            String tmp2 = Words[adjNode].substring(s, s+1);

            if(!tmp.equals(tmp2)){
                cnt++;
            }
        }

        return cnt==1;
    }
}

 

---

[예산]

https://programmers.co.kr/learn/courses/30/lessons/43237

코딩테스트 연습 - 예산

 

* 조건

1. 국가 예산 총액(M)과 각 지역마다 요청하는 예산(budgets)이 주어진다
2. 모든 요청을 M으로 감당할 수 있다면 요청한 금액을 그대로 배정한다
3. 만약 감당이 안된다면 상한선으로 대체한다 (지정한 상한선보다 높은 예산을 요청하면 상한선으로 대체)
4. 가능한 최대의 총 예산을 위한 상한선을 구한다

* 알고리즘

• 적절한 상한선을 구하고 비교: 이분 탐색

 

* 로직(Logic)

• 우선 오름차순 정렬을 한다
• 각 지역마다 요청한 합을 구한 뒤, M에 포함된다면 배열의 마지막 값을 리턴한다

 

• 기본적인 상한선을 answer = M / 지역 개수로 설정한다
• mid = (front=가장 최솟값 + rear=가장 최댓값) / 2로 하여 상한선을 탐색해간다
• 만약 상한선이 적용된 예산 총액이 M에 포함된다면 상한선을 mid로 업데이트 시켜주고, front = mid+1을 통해 그 다음 상한선을 높이도록 설정한다
• 만약 예산 총액이 M을 벗어난다면 rear = mid - 1을 통해 그 다음 상한선을 낮추도록 설정한다
• 이를 반복하다가 front > rear 라면 종료시킨다

 

import java.util.Arrays;

public class Problem_Budget {

    public static void main(String[] args) {
        int[] budgets = {120, 110, 140, 150};
        int M = 485;

        int answer = solution(budgets, M);
        System.out.println(answer);
    }

    public static int solution(int[] budgets, int M) {
        int answer = 0;
        int budgetSize = budgets.length;
        Arrays.sort(budgets);

        long sum = 0;
        for(int budget : budgets){
            sum += budget;
        }

        if(sum <= M) return budgets[budgetSize-1];

        int front = 1;
        int rear = budgets[budgetSize-1];
        while (front <= rear){
            sum = 0;
            int mid = (front + rear) / 2;

            for(int budget : budgets){
                if(budget > mid) sum += mid;
                else sum += budget;
            }

            if(sum > M) {
                rear = mid - 1;
            }
            else if(sum <= M){
                answer = mid;
                front = mid + 1;
            }
        }

        return answer;
    }
}

 

 

그 동안 이분 탐색이라고 하면 배열의 인덱스를 가지고만 했던지라 상한선 값을 이분탐색으로 좁혀나가는 응용에는 약했던거 같다. 응용되는 문제를 더 풀어봐야겠다는 생각을 했다.

 

그리고 같이 문제를 풀은 형은 오름차순 정렬의 특성을 이용해 하나씩 M에서 차감해나가며 평균(상한가)들을 갱신해주고, 그 평균을 넘어가는 곳부터는 모두 해당 상한가를 적용시키면 되기 때문에 그대로 리턴해주는 방법을 이용했다. 꼭 이분 탐색이 아니더라도 원리를 이용하는 방법도 효율적이라는 것을 깨달았다.