프로그래머스(여행 경로, 저울) - Java

[여행 경로]

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

코딩테스트 연습 - 여행경로

 

* 조건

1. 출발지와 도착지가 담긴 항공권이 입력된다
2. 주어진 항공권을 모두 사용해 모든 도시를 방문한다
3. 항상 ICN에서 출발한다
4. 가능한 경로가 2개 이상일 경우, 알파벳 순서가 앞서는 경로를 리턴한다

 

* 알고리즘

• 브루트포스

 

* 로직(Logic)

• 출발지가 같은 경우에는 도착지를 기준으로 사전순 오름차순 정렬을 한다(조건-4를 만족하기 위해)
• ICN으로 시작되는 곳을 찾고, 해당 항공권의 도착지를 경유지로 넘겨준다
• 모든 곳을 도착했을 경우를 list에 담아주고 종료시킨다

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;

public class Problem_TravelPath_ {

    static LinkedList<String> answerLists = new LinkedList<>();
    static boolean[] checked;
    static ArrayList<LinkedList<String>> lists;
    static boolean find = false;

    public static void main(String[] args) {
        String[][] tickets = {
                {"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL","SFO"}
        };

        String[] answer = solution(tickets);
        for(String ans : answer){
            System.out.print(ans + " ");
        }
    }

    public static String[] solution(String[][] tickets) {
        String[] answer;
        lists = new ArrayList<>();

        Arrays.sort(tickets, new Comparator<String[]>() {
            @Override
            public int compare(String[] o1, String[] o2) {
                if(o1[0].equals(o2[0])){
                    if(!o1[1].equals(o2[1])){
                        return o1[1].compareTo(o2[1]);
                    }
                    return o1[1].compareTo(o2[1]);
                }
                else return o1[0].compareTo(o2[0]);
            }
        });

        checked = new boolean[10001];
        int count = 0;
        findRoute("ICN", tickets, count);

        answer = new String[lists.get(0).size()];
        for(int i=0; i<answer.length; ++i){
            answer[i] = lists.get(0).get(i);
        }

        return answer;
    }

    private static void findRoute(String depart, String[][] tickets, int count) {
        if(find) return;
        answerLists.offer(depart);

        if(count == tickets.length){
            LinkedList<String> tmp = new LinkedList<>();
            for(String list : answerLists){
                tmp.add(list);
            }
            lists.add(tmp);
            find = true;

            return;
        }

        for(int i=0; i<tickets.length; ++i){
            if(tickets[i][0].equals(depart)){
                if(!checked[i]){
                    checked[i] = true;
                    findRoute(tickets[i][1], tickets, count+1);
                    checked[i] = false;
                }
            }
        }

        answerLists.removeLast();
    }
}

 

ArrayList의 remove 메소드를 써서 계속 애를 먹었다... ICN ICN이 담겨있는 경우에 remove를 사용하면 맨 뒤를 없애주는 것이 아닌 앞에 ICN을 지웠던 것이다... java에 대한 기본을 순간적으로 간과했다. 항상 유념하며 코드를 짜야겠다는 생각을 다시한번 하게 되었다... 이러지 말자 꼭

 

---

[저울]

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

코딩테스트 연습 - 저울

 

* 조건

1. 무게가 담긴 저울추가 주어진다
2. 저울추의 개수는 1 이상 10,000 이하이다
3. 각 추의 무게는 1 이상 1,000,000 이하이다
4. 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다

 

* 알고리즘

• 수학

 

* 로직(Logic)

• 오름차순 정렬을 한다
• 기준선(section)을 1로 시작하고 첫번째 배열의 추(w)와 비교한다
  • w <= section 이라면 section += w를 해준다
  • w > section 이라면 section을 리턴한다
• 해당 section과 해당 배열의 추와 비교했을 때, 추의 무게가 section에 포함되게되면 배열의 이전 인덱스들로 만들 수 있는 최대 합은 section-1이 된다. 즉, 1부터 section까지의 수를 만들 수 있다는 것이다.

 

import java.util.Arrays;

public class Problem_Scales {

    public static void main(String[] args) {
        int[] weight = {3, 1, 6, 2, 7, 30, 1};
        int answer = solution(weight);
        System.out.println(answer);
    }

    public static int solution(int[] weight) {
        int answer = 0;
        Arrays.sort(weight);

        int section = 1;
        for(int w : weight){
            if(section < w)
                return section;
            section += w;
        }

        return answer;
    }
}

 

<다시 풀어본 코드>

import java.util.Arrays;

public class Problem_TravelPath {

    public static void main(String[] args) {
        int[] weight = {3, 1, 6, 2, 7, 30, 1};
        int answer = solution(weight);
        System.out.println(answer);
    }

    public static int solution(int[] weight) {
        int answer = 0;
        Arrays.sort(weight);
       
        int section = 0;    //현재 추까지 만들 수 있는 최대 누적합        
        //누적 값 >= 해당 추 => 해당 추를 더한 값도 가능하고 그 이하의 값도 가능하다
        for(int w : weight){
            if(section + 1 < w) break;
            else if(section + 1 >= w){
                section += w;
            }
        }

        answer = section+1;
        return answer;
    }
}