1029. Two City Scheduling

https://leetcode.com/problems/two-city-scheduling/

• a와 b의 갭을 구한다.
• 위의 갭이 큰 값으로 descending 정렬한다.
• 갭순으로 정렬된것중에 중에 작은 값 기준으로 이렇게 정렬되어있다면
  • a b a a a b
  • a b a a b b 이렇게 분류해서 더한다. 왜냐하면 반틈씩 인터뷰를 진행해야한다고 나와있어서
• 위내용을 코딩화 하니깐 생각보다 복잡해졌음

Runtime: 2 ms
Memory Usage: 38.5 MB

class Solution {
     public int twoCitySchedCost(int[][] costs) {
        List<Schedule> list = new  ArrayList<Schedule> ();

        for( int i=0; i<costs.length; i++){
            list.add(new Schedule(costs[i][0], costs[i][1], Math.abs(costs[i][0] - costs[i][1]) ));
        }

        Collections.sort(list, new Comparator<Schedule>() {
            @Override
            public int compare(Schedule o1, Schedule o2) {
                return o2.gap - o1.gap;
            }
        });

        int len = costs.length/2;
        int acount = 0;
        int bcount = 0;
        int index =0;
        int minsum =0;
        while(acount<len && bcount <len){
            Schedule schedule = list.get(index++);
            if(schedule.a< schedule.b){
                acount++;
                minsum+= schedule.a;
            }else{
                bcount++;
                minsum+= schedule.b;
            }
        }

        if(acount != len){
            for (int i=index; i<list.size(); i++ ){
               minsum += list.get(i).a;
               acount++;
            }
        }

        if(bcount != len){
            for (int i=index; i<list.size(); i++ ){
                minsum += list.get(i).b;
                bcount++;
            }
        }
        return minsum;

    }

    class Schedule {
        int a;
        int b;
        int gap;

        Schedule(int a, int b, int gap){
            this.a = a;
            this.b = b;
            this.gap = gap;
        }
    }
}

두번째 코드

• 위의 로직을 조금더 깔끔하게 하는 방법
• solution을 보니깐 compare 하는부분에서 조금더 잘 정렬하던데 머리로 한 70% 이해했음. 코드 짜라고 하면 어려움
• 다음에 한번더 보면 좋을것 같은 문제

public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Math.abs(o2[0]- o2[1]) - Math.abs(o1[0]- o1[1]) ;
            }
        });

        int len = costs.length/2;
        int acount = 0; int bcount = 0; int index =0; int minsum =0;
        while(acount<len && bcount <len){
            int[] schedule = costs[index++];
            if(schedule[0]< schedule[1]){
                acount++;
                minsum+= schedule[0];
            }else{
                bcount++;
                minsum+= schedule[1];
            }
        }
        for (int i=index; i<costs.length; i++ ){
            if(bcount != len){
                minsum += costs[i][1];
                bcount++;
            }else{
                minsum += costs[i][0];
                acount++;
            }
        }
        return minsum;
     }