https://school.programmers.co.kr/learn/courses/30/lessons/42861

모든 섬이 통행 가능하도록 다리를 놓을 때 최소 비용을 구하는 문제이다.

주어진 정보는 모든 섬의 개수 n, 두 섬의 번호와 비용이 있는 costs 배열이다.

최소 비용을 구하는 문제이기 때문에 먼저 떠오르는 것은 cost가 저렴한 순으로 꺼내서 다리를 설치하는 것이다.

이때 만약 불필요한 다리라면 건설하지 않아야 한다. 여기서 불필요하다는 뜻은 해당 다리가 없어도 방문이 가능한 경우를 뜻한다.

여기서 이 판단을 하는 방법으로 집합을 쓰겠다. 같은 집합에 속한다면 즉 루트가 같다면 해당 집합은 모두 방문이 가능한 상태가 된다.

알고리즘의 초안은 다음과 같다.

1. 최소 비용의 다리를 꺼낸다. → PriorityQueue를 사용하면 간단해진다.
2. 이 다리에 추가되는 섬이 이미 같은 집합에 존재하면 다리를 설치하지 않는다. → 설치되는 경우 두 섬을 Union 연산을 통해 같은 집합으로 만든다.
3. pq가 비게 될 때까지 반복한다.

결국 Union-Find만 잘 구현하면 해결되는 문제다.

우선 Union-Find의 코드부터 보고 이해해 보자.

Union연산은 두 집합을 하나로 합치는 연산이고 Find는 특정 요소가 속하는 집합의 루트(대표)를 찾는 연산이다. 이 알고리즘은 주로 트리 구조를 사용하여 집합을 표현하게 된다.

public class UnionFind {
    private int[] parent; // 각 요소의 부모를 저장하는 배열
    private int[] rank;   // 트리의 높이를 저장하는 배열

    // 생성자: n개의 요소를 각각 독립된 집합으로 초기화
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for(int i = 0; i < n; i++) {
            parent[i] = i; // 초기에는 각 요소가 자기 자신을 부모로 가짐
            rank[i] = 1;   // 초기 트리의 높이는 1로 설정. 0으로 하는 경우도 있다.
        }
    }

    // Find 연산: x가 속한 집합의 대표(루트)를 찾음
    public int find(int x) {
        if(parent[x] != x) {
            parent[x] = find(parent[x]); // 경로 압축
        }
        return parent[x];
    }

    // Union 연산: x가 속한 집합과 y가 속한 집합을 합침
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if(rootX == rootY) {
            return; // 이미 같은 집합에 속해 있음
        }

        // 랭크를 비교하여 트리의 높이를 최소화
        if(rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if(rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX] += 1; // 트리의 높이가 증가
        }
    }

    // 두 요소가 같은 집합에 속해 있는지 확인
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

이해하기 어려운 알고리즘은 아니다. 여기서 주목해야 할 부분이 두 가지 있다.

1. 경로 압축 parent 배열은 자신의 부모 노드를 가지고 있다. parent [idx]가 idx의 부모를 뜻한다. 하지만 바로 자신의 부모를 가지고 있으면 탐색에 시간이 증가하게 된다. 이를 효율화하기 위해 자신의 부모가 아닌 집합의 루트를 가지고 있게 하는 방식이 경로 압축이다.
2. Rank 개념 트리의 높이가 커질수록 연산이 비효율적이 됩니다. 따라서 Rank의 개념을 도입해 높이를 최소화한다. Union 연산 시, 두 집합의 트리 높이를 비교하여 작은 트리를 큰 트리 아래에 합친다. 높이가 같다면 어디에 합쳐도 상관없다.

이 알고리즘을 통해 문제를 다음과 같이 풀 수 있습니다.

import java.util.*;

class Solution {
    
    public int solution(int n, int[][] costs) {
        
        int[] parent = new int[n];
        int[] rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        int answer = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
        for (int[] info : costs) {
            pq.add(info);
        }
        
        while (!pq.isEmpty()) {
            int[] info = pq.poll();
            int id1 = info[0];
            int id2 = info[1];
            int cost = info[2];
            
            // 이미 같은 집합에 속해있다면 다리를 놓는것은 낭비다.
            if (find(id1, parent) == find(id2, parent)) continue;
            
            union(id1, id2, parent, rank);
            
            answer += cost;
        }
        

        return answer;
    }
    
    private int find(int x, int[] parent) {
        if (x != parent[x]) {
            parent[x] = find(parent[x], parent);
        }
        return parent[x];
    }
    
    private void union(int x, int y, int[] parent, int[] rank) {
        int rootX = find(x, parent);
        int rootY = find(y, parent);
        
        if (rootX == rootY) return;
        
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

코딩테스트 연습 - 영어 끝말잇기 | 프로그래머스 스쿨 (programmers.co.kr)

문제 조건

1. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
2. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작
3. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어.
4. 이미 등장한 단어는 사용 불가
5. 한 글자는 안된다
6. 탈락자가 생기지 않는다면 [0, 0]을 반환한다.

이때 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는가.

문제의 흐름대로 구현

문제 조건을 읽으며 정리한 단서들을 조합해 보자.

우선은 앞에서부터 순회하며 읽는다.

또한 순환하고 있기 때문에 % 연산을 사용한다.

문자의 비교를 위해 charAt을 사용해서 비교를 한다.

이미 등장했던 단어를 빠르게 검색하기 위해 Hash 기반의 Set을 사용하면 될 것 같다.

예외로 한 글자 조건이 있다.

자신의 턴을 관리해줘야 한다. 이는 Map을 통해 자신의 번호 : 턴으로 관리를 하면 빠르게 찾고 수정할 수 있다.

import java.util.*;

class Solution {
    public int[] solution(int n, String[] words) {
        Map<Integer, Integer> turn = new HashMap<>();
        Set<String> wordSet = new HashSet<>();
        for (int i = 1; i <= n; i++) {
            turn.put(i, 1);
        }
        
        // 첫 턴 예외
        turn.put(1, 2);
        wordSet.add(words[0]);
        int id = 1;
        boolean isEnd = true;
        
        for (int i = 1; i < words.length; i++) {
            id = i % n + 1;
            String prevWord = words[i - 1];
            String word = words[i];
            
            // 탈락 조건
            if (word.length() == 1 ||
                wordSet.contains(word) ||
                prevWord.charAt(prevWord.length() - 1) != word.charAt(0)) {
                isEnd = false;
                break;
            }
        
            turn.put(id, turn.get(id) + 1);
            wordSet.add(word);
        }
        
        if (isEnd) return new int[]{0, 0};
        
        int[] answer = {id, turn.get(id)};
        
        return answer;
    }
}

코드 개선

문제의 흐름을 따라서 구현하다 보면 O(N)의 시간복잡도로 풀이가 가능하다.

이 풀이에서 따져보자면 turn을 관리하고 있는 Map 같은 경우에는 굳이 필요하지 않다.

그리고 첫 턴을 처리하는 것이 코드의 명확성을 떨어뜨린다고 생각한다.

n을 통해서 현재 턴을 (i/n + 1)로 처리하면 공간복잡도를 개선할 수 있을 것 같다.

또한 리턴을 break 시점에 하는 것이 더 빠른 명확한 처리가 될 것 같다.

문제 조건에서 1글자 단어는 인정되지 않는다고 했는데 제한 사항을 보면 단어의 길이가 2 이상 50 이하라는 제한이 있다. 따라서 1글자 검증 과정을 불필요하다.

import java.util.*;

class Solution {
    public int[] solution(int n, String[] words) {
        Set<String> usedWords = new HashSet<>();
        usedWords.add(words[0]);
        
        for (int i = 1; i < words.length; i++) {
            if (usedWords.contains(words[i]) ||
                words[i].charAt(0) != words[i-1].charAt(words[i - 1].length() - 1)) {
                return new int[]{(i % n) + 1, (i / n) + 1};
            }
            usedWords.add(words[i]);
        }
        
        return new int[]{0, 0};
    }
}

개선사항을 통해 훨씬 읽기 좋은 코드가 됐다고 생각한다.