1971 Find if Path Exists in Graph

• 문제 요약: 주어진 두 노드(start, end)가 연결되어있는지 확인하라.

Union Find 란

• Disjoint Set 한다면
  • 자신의 값을 부모 노드 위치값으로 바꿔준다.

Disjoint Set 종류

• Quick Find

  • public int find(int x) {
        return root[x];
    }
    
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            for (int i = 0; i < root.length; i++) {
                if (root[i] == rootY) {
                    root[i] = rootX;
                }
            }
        }
    }
    

• Quick Union -> 성능 better

  • public int find(int x) {
        while (x != root[x]) {
            x = root[x];
        }
        return x;
    }
    
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            root[rootY] = rootX;
        }
    }
    

Union Find without Rank

• 
• 
• 
• Quick Find 보다는 Quick Union 이 성능이 좋다.

class Solution {
    public boolean validPath(int n, int[][] edges, int start, int end) {
        UnionFind uf = new UnionFind(n);

        for(int[] edge : edges){
            uf.union(edge[0], edge[1]);
        }

        return uf.areConnected(start, end);
    }
}

class UnionFind {
    private int[] root;

    public UnionFind(int size) {
        root = new int[size];
        for (int i = 0; i < size; i++) {
            root[i] = i;
        }
    }

    public int find(int x) {
        while (x != root[x]) { // 배열 위치 값과 안에 값이 같을 때까지 반복 (즉, 뿌리 찾기)
            x = root[x];
        }
        return x;
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            root[rootY] = rootX; // y의 뿌리의 위치에 x의 뿌리 위치를 넣어준다.
        }
    }

    public boolean connected(int x, int y) { 
        return find(x) == find(y); // 각 root 값 찾아오기 
    }
}

Union Find with Rank

• Worst Cast에 대한 대응 방안
• 탐색하는 시간을 줄이고자, 노드 묶음들을 Union할때 긴쪽이 작은쪽을 흡수하는 방식.
• LeetCode Explore
• 최악 사례: 0 1 2 3 4 5 6 7 -> (6 7) (5 6) (4 5) (3 4) (2 3) (1 2) (0 1) 경우

class Solution {
    public boolean validPath(int n, int[][] edges, int start, int end) {
        UnionFind uf = new UnionFind(n);
        for(int[] edge : edges){
            uf.union(edge[0], edge[1]);
        }
        return uf.areConnected(start, end);
    }
}

class UnionFind { 
    private int[] root;
    private int[] rank; // RANK 추가 

    public UnionFind(int size) {
        root = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            root[i] = i;
            rank[i] = 1; 
        }
    }

    public int find(int x) { // find는 똑같다.
        while (x != root[x]) {
            x = root[x];
        }
        return x;
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) { // 한쪽이 클 경우 다른 쪽을 흡수, 높이 변경은 없다.
                root[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) { 
                root[rootX] = rootY;
            } else {
                root[rootY] = rootX;
                rank[rootX] += 1; // 0-1, 1-2 두개 연결할 경우 0-1-2 되니 +1 해줘야 한다. 높이 변경 필요.
            }
        }
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

67 Add Binary

문제 요약: 2진수 String을 더해 2진수를 리턴하라.

내풀이

• 두개의 길이를 맞춰준다.
  • 이유: 뒤에서 부터 더해야되는데, 포인터 여러개 쓰면 복잡하니까.

// Runtime: 2 ms, faster than 77.17% of ~
// Memory Usage: 38.8 MB, less than 80.80% of ~
public String addBinary(String a, String b) {
    if (a.length() < b.length()) return addBinary(b, a); 

    StringBuilder sb = new StringBuilder();
    int zeroNum = a.length() - b.length();
    for (int i = 0; i < zeroNum; i++) sb.append("0");
    sb.append(b);
    b = sb.toString();

    StringBuilder ret = new StringBuilder();
    int carry = 0;

    for (int i = a.length() - 1; i >= 0; i--) {
        int sum = carry + Character.getNumericValue(a.charAt(i)) + Character.getNumericValue(b.charAt(i));
        if (2 <= sum) carry = 1;
        else carry = 0;
        ret.append(sum % 2);
    }
    if(carry != 0) ret.append("1");

    return ret.reverse().toString();
}

풀이1 - built-in library

• radix -> 2로 설정
• 문제
  • 제약조건: 1 <= a.length, b.length <= 104
  • Input이 이럴 경우 "10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101"
  • NumberFormatException
  • Integer.parseInt("값", 2)
    • 값에는 int 범위만 들어가야되는데 위는 2^94 이므로 Integer이 다룰 수 있는 범위인 2^31을 벗어난다.

public String addBinary1(String a, String b) {
    return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));
}

풀이2

• 포인터 이용

public String addBinary3(String a, String b) {
    int aLen = a.length(), bLen = b.length();
    if (aLen < bLen) return addBinary3(b, a); //
    // 이 아래로 aLen가 크거나 같다는게 보장됨

    StringBuilder sb = new StringBuilder();
    int carry = 0, j = bLen - 1; // 여기선 carry에 모든 값을 더한다.
    for(int i = aLen - 1; i > -1; --i) { //긴 스트링 기준으로 돈다.
        if (a.charAt(i) == '1') ++carry;
        if (j > -1 && b.charAt(j--) == '1') ++carry;

        if (carry % 2 == 1) sb.append('1');
        else sb.append('0');

        carry /= 2;
    }
    if (carry == 1) sb.append('1');
    sb.reverse();

    return sb.toString();
}

풀이3 - 제일 깔끔

• 16진수 BigInteger
• a: 1 1 1, b: 1
• 1차
  • answer: 1 1 0 carry: 0 1 0 x: 1 1 0 y: 0 1 0
• 2차
  • answer: 1 0 0 carry: 1 0 0 x: 1 0 0 y: 1 0 0
• 3차
  • answer: 0 0 0 carry: 1 0 0 0 x: 0 0 0 y: 1 0 0 0
• 4차
  • answer: 1 0 0 0 carry: 0 0 0 0 x: 1 0 0 0 (답) y: 0 0 0 0

import java.math.BigInteger;
class Solution {
    public String addBinary(String a, String b) {
        BigInteger x = new BigInteger(a, 2);
        BigInteger y = new BigInteger(b, 2);
        BigInteger zero = new BigInteger("0", 2);
        BigInteger carry, answer;
        while (y.compareTo(zero) != 0) {
            answer = x.xor(y);
            carry = x.and(y).shiftLeft(1);
            x = answer;
            y = carry;
        }
        return x.toString(2);
    }
}