Today I Learned

오늘 할일
1. LeetCode
2. 창엔 1일차

오늘 한일
1. LeetCode

• 1466. Reorder Routes to Make All Paths Lead to the City Zero에서 효율성을 가장 높이기 위한 방법은 connections을 순회하면서 change count를 바로 세는 것이다. 고로 기본적인 틀을 작성해두고 TDD방식으로 접근해보았다.

class Solution {
    public int minReorder(int n, int[][] connections) {
        if(connections.length<=2)
            return 0;
        int result=0;
        ArrayList<ArrayList<Integer>> lists=new ArrayList<ArrayList<Integer>>();
        //무방향 리스트 구축
        for(int[] elem : connections){
            int v1=elem[0], v2=elem[1];
            int flag=0;
            for(List list : lists){
                if(list.contains(v1) && !list.contains(v2)){
                    list.add(v2);
                    flag=1;
                    result++;
                    break;
                }
                if(list.contains(v2) && !list.contains(v1)){
                    list.add(v1);
                    flag=1;
                    break;
                }
            }
            if(flag==0){//새로 만들어야한다면
                ArrayList new_list=new ArrayList<Integer>();
                new_list.add(v1); new_list.add(v2);
                lists.add(new_list);
            }
        }
        //0을 기준으로 방향확인
        if(n%2!=1 && connections.length%2!=0)
            result++;
        return result;
    }
}

MLE와 TLE가 발생했던 41번 테스트 케이스는 통과했지만 바로 다음 테스트 케이스에서 실패하고 말았다. 본질적인 해결 방법이 필요해보인다.