BLOG :||

import java.util.*;

class Bridge implements Comparable<Bridge>{
    int cost;
    int from;
    int to;
    public Bridge(int cost, int from, int to) {
        this.cost = cost;
        if(from < to) {
            this.from = from;
            this.to = to;
        }
        else {
            this.from = to;
            this.to = from;  
        }
    }
    @Override
    public int compareTo(Bridge b) {
        if(b.cost < cost)
            return 1;
        else if(cost < b.cost)
            return -1;
        else
            return 0;
    }
}
class Solution {
    int[] parent;
    public int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n];
        
        for(int i = 0; i < n;++i)
            parent[i] = i;
        
        List<Bridge> list = new ArrayList<>();
        
        for(int[] cost : costs)
            list.add(new Bridge(cost[2], cost[0], cost[1]));
        
        Collections.sort(list);
        
        for(Bridge bridge : list) {
            if(!isSameParent(bridge.from, bridge.to)) {
                answer += bridge.cost;
                setParent(bridge.from, bridge.to);
            }
        }
        return answer;
    }
    public boolean isSameParent(int i, int j) {
        if(getParent(i) != getParent(j))
            return false;
        return true;
    }
    public int getParent(int i) {
        if(parent[i] != i) {
            return getParent(parent[i]);
        }
        return parent[i];
    }
    public void setParent(int i, int j) {
        if(getParent(i) != i) {
            parent[getParent(j)] = getParent(i);
        } 
        else if(getParent(j) != j) {
            parent[getParent(i)]  = getParent(j);
        }
        else {
            parent[j] = parent[i];
        }
    }
}

크루스칼 알고리즘을 써야 하는 문제이다.

처음 봤을 때는 억... 했지만 크루스칼 알고리즘을 다시 복기하고 나니까 크게 어려운 문제는 아니었다.

크루스칼 알고리즘을 써야하는 문제는 이렇게 생겼구나 하고 기억만 해두면 문제는 없을 것 같다.

까먹지 말아야 할 건 setParent에서 parent[j] = ~~~~가 아니라 parent[getParent(j)] = ~~~~~가 되야 한다는 점.

서로 다른 그룹을 연결하기 위해서는 최상위 부모가 되는 노드끼리 연결을 해주어야 하기 때문.

스터디 공부 하고 관련 문제를 풀어봤는데 재미는 있는데... 이거에 시간 쓸 때가 아닌데 어휴

class Solution {
    public int solution(String name) {
        int answer = 0;
        int nameLen = name.length();
        boolean[] changed = new boolean[nameLen];
        int tmp = 0;
        int trueCount = 0;
        for(int i = 0; i<nameLen;++i) {
            if(name.charAt(i) != 'A') {
                tmp = name.charAt(i)-'A';
                if(tmp < 13)
                    answer += tmp;
                else 
                    answer += (26-tmp);
                changed[i] = true;
                trueCount++;

            }
        }
        changed[0] = false;
        trueCount--;
        
        int min = nameLen;
        int minIndex = -1;
        //0,1,2,3
        //4-3-cursor = 1
        //4-2-cursor = 2
        //4-1-cursor = 3
        // 
        int cursor = 0;
        int distance = 0;
        while(trueCount > 0) {
            min = nameLen;
            minIndex = -1;
            
            for(int i = 0; i<nameLen;++i) {
                if(changed[i] == true) {
                    distance = (cursor > i) ? cursor-i:i-cursor;
                    if(cursor < i) {
                        distance = (nameLen-distance < distance) ? nameLen-distance : distance;
                    }
                    if(min > distance) {
                        min = distance;
                        minIndex = i;
                    }
                }
            }
            changed[minIndex] = false;
            answer += min;
            trueCount--;
            cursor = minIndex;
            
        }
        
        return answer;
    }
}

아 이게 어떻게 레벨2짜리 문제인건지..;;

예전에 문제를 풀었을 때는 글자를 바꾸고 한 칸 옮기고 글자를 바꾸고 한 칸 옮기는 식으로 했었는데 책을 본 효과인지는 모르겠지만.. 글자가 다른 경우를 미리 다 처리하고 나서 옮기는 것에 대해서만 고려할 수 있도록 코드를 짜보니 확실히 깔끔해졌다.

다만 테스트케이스 11에서 틀렸다고 나오는데 다른 사람들 질문 내용을 봐도 감이 안온다. 그리디 알고리즘이라고 할 때 가장 가까운 값으로 이동을 하는 것 외에 고려할게 없을텐데.. 문제가 약간 이상하다고 생각해서 여기까지 하고 넘긴다.

지금은 마땅히 생각나는 문제점을 못찾고 있으니 다음에 한 번 더 봐야겠다.

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        int[] clothes = new int[n];
        for(int l : lost) {
            clothes[l-1]--;
        }
        for(int r : reserve) {
            clothes[r-1]++;
        }
        
        for(int i = 0; i<clothes.length;++i) {
            if(clothes[i] >0 && i > 0 && clothes[i-1] == -1) {
                clothes[i-1]++;
                clothes[i]--;
                System.out.println(i+ " "+ (i-1));
            }
            else if(clothes[i] > 0 && i+1 <clothes.length && clothes[i+1] == -1) {
                clothes[i+1]++;
                clothes[i]--;
                System.out.println(i+ " "+ (i+1));
            }
            /*
            if(clothes[i] > 0 && i+1 <clothes.length) {
                clothes[i+1]++;
                clothes[i]--;
            }*/
            
        }
        for(int i : clothes) {
            System.out.print(i);
            if(i >= 0)
                answer++;
        }
        return answer;
    }
}

처음 풀 때 어디서 꼬였었는데 넘겼다가 오늘 다시 풀어봤다.

clothes[]를 초기화하면 기본적으로 다 0이 들어가 있으므로 0을 옷을 1장 보유한 상태로 가정한다.

도둑맞은걸 빼고 여분을 더해준 뒤해 알고리즘이 시작된다.

왼쪽에서 오른쪽으로 진행될 예정이기 때문에 왼쪽을 우선적으로 빌려주고 왼쪽이 옷을 가지고 있을 경우, 오른쪽에 빌려주는 형태로 진행이 된다.

여분을 계속 우측으로 넘기면 좋지 않을까 싶었지만 옷은 없는 사람한테만 직접 빌려줘야 하나보다.