[LeetCode] 문제 복기(886번, 390번,684번,1685번,983번)

LeetCode를 풀면서 고생했던(?) 문제와 재밌게 풀었던 문제들을 돌아보는 시간.

886. Possible Bipartition

---

서로 함께할 수 없는 번호들이 주어지고 return으로 2개의 그룹을 만들 수 있는지를 넘겨줘야하는 문제다.

탐색으로 풀어야겠다고 생각하고 접근까지는 했으나 상태를 3개로 구분하지 못해서 헤맸다. (돌아보면 진짜 아무것도 아닌데) 방문, 미방문이 아니라 미방문, 그룹1, 그룹2 이런식으로 3가지의 상태를 통해 문제를 풀었어야했다.

 

class Solution {
    public static boolean possibleBipartition(int N, int[][] dislikes) {

        int[] peopleGroup = new int[N+1];
        Map<Integer, List<Integer>> graph = new HashMap<>();

        for (int[] dislike : dislikes) {
            if(!graph.containsKey(dislike[0])) graph.put(dislike[0], new ArrayList<>());
            if(!graph.containsKey(dislike[1])) graph.put(dislike[1], new ArrayList<>());

            graph.get(dislike[0]).add(dislike[1]);
            graph.get(dislike[1]).add(dislike[0]);

        }
        for (int[] dislike : dislikes) {
            if(peopleGroup[dislike[0]] ==0 && !dfs(graph,peopleGroup,dislike[0] , 1)){
                return false;
            }
        }

        return true;
    }

    public static boolean dfs(Map<Integer,List<Integer>> graph, int[] peopleGroup, int curPerson, int groupNumber) {


        if(peopleGroup[curPerson] == groupNumber) return false;
        peopleGroup[curPerson] = groupNumber; // 그룹 할당
        List<Integer> haters = graph.get(curPerson);// curPerson을 싫어하는 사람


        for (Integer hater : haters) { // curPerson 싫어하는 사람 순회
            if (peopleGroup[curPerson] == peopleGroup[hater]) return false; // curPerson의 그룹 == hater-1 group
            if (peopleGroup[hater] == 0 && !dfs(graph, peopleGroup, hater, -groupNumber)) return false;

        }
        return true;

    }
}

---

390. Elimination Game

---

1~n까지의 숫자가 배열에 있을때, 좌측에서 퐁당, 우측에서 퐁당으로 숫자를 제거해 나간다. 반환값으로 마지막에 남는 숫자를 출력하는 문제다. 

 

max는 현재 배열에 존재하는 최대값을 담고 있다. 

배열의 문자를 좌측에서 제거를 시도하면서 배열에 남은 문자가 홀수개면 max는 항상 변경된다. 

매회차를 수행할수록 배열에 남아있는 숫자들은 2^진행된 회차만큼의 간격이 벌어진다.

max는 좌측에서 제거를 시작하면서 배열에 남은 숫자가 홀수개일때만 변경된다.

class Solution {
    public int lastRemaining(int n) {
        
        if(n==1) return 1;

        n = n%2 == 1 ? n-1 : n; // 짝수화
        int max = n;
        n = n/2 + n%2;
        int count = 1;
        boolean startLeft= false;
        while(true){
            if( n <= 1 ) return max;
            if((startLeft && n%2 == 1) || (!startLeft) ){
                max = max - (int) Math.pow(2,count);    
            }
            n = n/2;
            count++;
            startLeft = !startLeft;
        }
        return max;
    }
}

---

684. Redundant Connection

---

주어진 Graph에서 특정 edge를 끊어 Loop가 불가능한 트리를 만드는게 목표. 반환값으로 끊어야 하는 edge를 출력해야한다. 후보가 여러개라면 가장 마지막에 입력된 edge를 출력해야한다.

 

edge를 하나씩 연결하며 graph를 생성하는데 graph가 생성되고 나면 graph에 Loop가 존재하는지 검사하도록 했다. 

edge를 모두 연결한채로 Loop가 존재하는지 찾는 코드를 작성했었는데 문제의 조건인 "후보가 여러개일땐 가장 마지막에 입력된 Edge를 출력하라" 때문에 graph 생성중에 Loop 여부를 판단하도록 코드를 짰다.

class Solution {
    
    public static boolean dfs(Map<Integer,List<Integer>> graph, int[] visited,int curNode,int preNode){

        if(visited[curNode] == 1) {
            return true;
        }
        else {
            visited[curNode] = 1;
            List<Integer> integers = graph.get(curNode);
            for (Integer integer : integers) {
                if(preNode != integer){
                    if(dfs(graph , visited , integer, curNode)){
                        return true;
                    }
                }

            }
        }
        return false;
    }
    
    
    public int[] findRedundantConnection(int[][] edges) {
        Map<Integer,List<Integer>> graph = new HashMap<>();
        int[] result = new int[2];
        for (int[] edge : edges) {
            if(!graph.containsKey(edge[0])) graph.put(edge[0], new ArrayList<>());
            if(!graph.containsKey(edge[1])) graph.put(edge[1], new ArrayList<>());
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);


            int[] visited = new int[edges.length+1];
            if(dfs(graph,visited,edge[0] , 0)){
                return new int[]{edge[0] , edge[1]};
            }

        }

        return result;
    }
}

---

1685. Sum of Absolute Differences in a Sorted Array

---

쉬울줄 알고 덤벼들었다가 고생한 문제.

배열을 순회하면 각 index의 값을 모든 원소와 뺄셈을 수행하며 결과의 절대값을 새로운 배열에 기록하는 문제이다.

단순한 방법으로 풀면 답은 나오는데 시간초과가 발생한다. 

핵심은 기준 index의 좌측과 우측을 각각 구한 다음에 합쳐줘야 한다는 것.

class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        int[] result= new int[nums.length];
        int[] partSum = new int[nums.length];
        partSum[0] = nums[0];
        for(int i=1; i<nums.length; i++){
            partSum[i] = partSum[i-1] + nums[i];
        }
        
        
        for(int i=0; i<nums.length; i++){

            // 좌측 상수합 - 기준합
            int leftSum = partSum[i]; // i까지의 합 ( i포함 )
            int rightSum = partSum[nums.length-1] - partSum[i]; // 끝부터 i+1 까지
            result[i] = Math.abs(leftSum - (nums[i]*(i+1))) + Math.abs(rightSum - (nums[i] * (nums.length-i-1)));

        }
        return result;
    }
}

---

983. Minimum Cost For Tickets

---

못풀고 결국 정답 확인한 문제. 알고보니 DP를 활용해야하는 문제였다.

days에 주어진 날짜를 여행해야 할때 발생하는 최소비용을 구하는 문제이다.

 

처음엔 아래와 같이 재귀적으로 모든 경우의 수를 다 검사할 수 있도록 했지만 역시나 시간초과

class Solution {

    public static int recursive(int[] days, int[] costs , int startIndex,int sumCost ){

        if(startIndex >= days.length){
            return sumCost;
        }else{

            // 1-day Ticket
            int a = recursive(days,costs,startIndex+1,sumCost+costs[0]);

            // 7-days Ticket
            int nextIndex = -1;
            for(int i=startIndex; i<days.length; i++){
                if( days[i] >= days[startIndex] + 7){
                    nextIndex = i;
                    break;
                }
            }
            int b = recursive(days,costs,nextIndex == -1 ? days.length : nextIndex ,sumCost+costs[1]);
            

            // 30-days Ticket
            int nextIndex2 = -1;
            for(int i=startIndex; i<days.length; i++){
                if( days[i] >= days[startIndex] + 30){
                    nextIndex2 = i;
                    break;
                }
            }
            int c = recursive(days,costs,nextIndex2 == -1 ? days.length : nextIndex2 ,sumCost+costs[2]);

            return Math.min(a,Math.min(b,c));

        }

    }


    public int mincostTickets(int[] days, int[] costs) {

        return recursive(days, costs , 0,0 );

    }
}

 

DP를 활용한 코드. dp[i] = i날짜 까지 여행을 할때 발생하는 최소비용

코드의 포인트는 dp[i]를 구할때 dp[i-1], dp[i-7], dp[i-30] 세개를 확인해야한다는 것.

class Solution {

    public int mincostTickets(int[] days, int[] costs) {

        // i 날짜까지 커버하는데 사용된 최소비용
        int lastDay = days[days.length-1];
        int[] dp = new int[lastDay+1];
        boolean[] isTravelDay = new boolean[lastDay+1];
        for (int day : days) isTravelDay[day] = true;


        for(int i=1; i<=lastDay; i++){
            if(!isTravelDay[i]) dp[i] = dp[i-1];
            else{
                dp[i] = dp[i-1] + costs[0]; // 1-day 티켓을 이용해 i날짜까지 도착
                dp[i] = Math.min(dp[Math.max(i-7,0)] + costs[1] , dp[i]); // 7-day 티켓을 이용해 i날짜까지 도착
                dp[i] = Math.min(dp[Math.max(i-30,0)] + costs[2] , dp[i]); // 30-day 티켓을 이용해 i날짜까지 도착
            }
        }
        return dp[lastDay];

    }
}