잡다한 배똥월드

import java.util.*;
class Solution {
    int col, row;
    ArrayList<String> arr;
    ArrayList<String[]> answer;
    public int solution(String[][] relation) {
        answer = new ArrayList<>();
        col = relation[0].length;
        row = relation.length;
        arr = new ArrayList<>();
        
        //후보키 조합 만들기
        create(0, "");
        
        //길이 기준으로 오름차순 정렬
        Collections.sort(arr, new Comparator<String>(){
            @Override
            public int compare(String a, String b) {
                return a.length() - b.length();
            }
        });
        
        //최소성 확인하고 유일성 확인
        for (int i = 0; i < arr.size(); i++) {
            String[] s = arr.get(i).split("");
            if (check(s)) make(relation, s);
        }
        
        return answer.size();
    }
    
    //유일성 확인 함수
    public void make(String[][] r, String[] s) {
        HashMap<String, Integer> m = new HashMap<>();
        
        //글자를 만들면서 중복이 있는지 없는지 파악
        for (int i = 0; i < row; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < s.length; j++) {
                sb.append(r[i][Integer.parseInt(s[j])]);
            }
            
            String str = sb.toString();
            if (m.getOrDefault(str, 0) != 0) return;
            
            m.put(str, 1);
        }
        
        answer.add(s);
    } 
    
    //최소성 확인 함수
    public boolean check(String[] s) {
        List<String> list = Arrays.asList(s);
        
        //answer이랑 비교하면서 answer에 있는 조합이 s에 들어 있는지를 파악함
        for (int i = 0; i < answer.size(); i++) {
            String[] a = answer.get(i);
            if (a.length > s.length) continue;
            boolean value = false;
            for (int m = 0; m < a.length; m++) {
                if (list.indexOf(a[m]) == -1) {
                    value = true;
                    break;
                }
            }
            
            if (!value) return false;
        }
        
        return true;
    }
    
    public void create(int num, String s) {
        for (int i = num; i < col; i++) {
            StringBuilder temp = new StringBuilder(s);
            temp.append(i);
            String str = temp.toString();
            arr.add(str);
            create(i + 1, str);
        }
    }
}

import java.util.*;
class Solution {
    Point[][] points;
    int[][] table;
    int n, m;
    boolean answer;
    public boolean solution(int[][] key, int[][] lock) {
        answer = false;
        n = key.length;
        m = lock.length;
        table = new int[m + (n-1)*2][m + (n-1)*2];
        
        int spin = 0;
        int start = n-1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (key[i][j] == 1) spin++;
            }
        }
        
        //돌기가 있는 점들 0도, 90도, 180도, 270도 버전으로 미리 배열에 담아놓기
        points = new Point[4][spin];
        int position = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (key[i][j] == 1) {
                    points[0][position] = new Point(i, j);
                    points[1][position] = new Point(j, n-i-1);
                    points[2][position] = new Point(n-i-1, n-j-1);
                    points[3][position] = new Point(n-j-1, i);
                    position++;
                }
            }
        }
        
        //table은 key가 상하좌우 대각선 모두 다 넣을 수 있도록 범위를 넓힌 상태에서
        //lock 부분 체크해놓기
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                table[i+n-1][j+n-1] = lock[i][j];
            }
        }
        
        //key 넣으면서 체크하기
        for (int i = 0; i < table.length - (n-1); i++) {
            for (int j = 0; j < table.length - (n-1); j++) {
                for (int k = 0; k < 4; k++) {
                    if (call(i, j, k)) return true;
                }
            }
        }
        
        return false;
    }
    
    //만약 func함수 호출 후 answer이 true가 된다면 그냥 바로 리턴하기
    public boolean call(int x, int y, int index) {
        func(x, y, n-1, index, 0);
        if (answer) return true;
        
        return false;
    }
    
    public void func(int sX, int sY, int sLock, int index, int num) {
    	//num과 points[index]의 길이가 같으면 key의 돌기를 다 돈 것이기 때문에
        //lock 부분이 전부 1이면 true 아니면 false 리턴
        if (num == points[index].length) {
            for (int i = sLock; i < sLock+m; i++) {
                for (int j = sLock; j < sLock+m; j++) {
                    if (table[i][j] == 0 || table[i][j] == 2) return;
                }
            }
            
            answer = true;
            return;
        }
        
        Point p = points[index][num];
        
        if (table[sX + p.x][sY + p.y] == 0) {
            table[sX + p.x][sY + p.y]++;
            func(sX, sY, sLock, index, num+1);
            table[sX + p.x][sY + p.y]--;
        }
        
    }
}

class Point {
    int x, y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

import java.util.*;
class Solution {
    //만들어지는 글자, 점수
    HashMap<String, ArrayList<Integer>> table;
    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];
        table = new HashMap<>();
        
        //info 글자대로 만들 수 있는 조건 만들고, 해당 조건에 대해 점수 넣기
        for (int i = 0; i < info.length; i++) {
            String[] temp = info[i].split(" ");
            func(temp, 0, new StringBuilder());
        }
        
        //점수 오름차순 정렬
        for (String key : table.keySet()) {
            ArrayList<Integer> arr = table.get(key);
            Collections.sort(arr);
            table.put(key, arr);
        }
        
        //query에 맞는 것 보내기
        for (int i = 0; i < query.length; i++) {
            String[] temp = query[i].split(" ");
            StringBuilder sb = new StringBuilder(temp[0]);
            sb.append(temp[2]);
            sb.append(temp[4]);
            sb.append(temp[6]);
            
            //점수에 대해 이분탐색 하기
            ArrayList<Integer> arr = table.getOrDefault(sb.toString(), new ArrayList<>());
            int num = Integer.parseInt(temp[7]);
            int start = 0;
            int end = arr.size();
            
            while (start < end) {
                int mid = (start + end) / 2;
                if (arr.get(mid) >= num) {
                    end = mid;
                } else {
                    start = mid + 1;
                }
            }
            answer[i] = arr.size() - start;
        }
        return answer;
    }
    
    public void func(String[] l, int n, StringBuilder sb) {
        if (n == l.length - 1) {
            String str = sb.toString();
            ArrayList<Integer> p = table.getOrDefault(str, new ArrayList<>());
            p.add(Integer.parseInt(l[4]));
            table.put(str, p);
            return;
        }
        
        StringBuilder sb1 = new StringBuilder(sb);
        StringBuilder sb2 = new StringBuilder(sb);
        sb1.append(l[n]);
        sb2.append("-");
        func(l, n+1, sb1);
        func(l, n+1, sb2);
    }
}

import java.util.*;
class Solution {
	//이름에 대한 부모와 자기 포인트 확인용 해시맵
    HashMap<String, Family> map;
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] answer = new int[enroll.length];
        map = new HashMap<>();
        
        //본인에 대한 부모와 포인트 설정
        for (int i = 0; i < enroll.length; i++) {
            Family f = new Family(referral[i], 0);
            map.put(enroll[i], f);
        }
        
        //센터는 따로 enroll에 없기 때문에 따로 추가하기
        map.put("-", new Family("", 0));
        
        for (int i = 0; i < seller.length; i++) {
            int money = amount[i] * 100; //판매금액
            String son = seller[i]; //판매자
            
            //센터까지 올라가야하기 때문에 while문 활용
            while (true) {
            	//부모에게 넘길 돈 현재 금액의 10%
                int parentMoney = (int) (money * 0.1);
                
                //부모에게 주고 남은 돈
                int sonMoney = money - parentMoney;
                
                //남은 돈은 추가하고, 부모 이름 리턴
                son = map.get(son).addPoint(sonMoney);
                
                //부모에게 넘길 돈으로 현재 금액 설정하기
                money = parentMoney;
                
                //만약 부모에게 넘길 돈이 0원이거나 부모가 없는 경우(센터일 경우) while문 탈출
                if (son.equals("") || money == 0) break;
            }
        }
        
        //enroll로 answer에 포인트 값 넣기
        for (int i = 0; i < enroll.length; i++) {
            answer[i] = map.get(enroll[i]).point;
        }
        return answer;
    }
}

class Family {
    String parent;
    int point;
    public Family(String parent, int point) {
        this.parent = parent;
        this.point = point;
    }
    
    public String addPoint(int point) {
        this.point += point;
        return parent;
    }
}

class Solution {
    public int solution(int n, int a, int b) {
        int answer = 0;
        
    	//항상 a가 작고, b가 크다는 조건이 없기 때문에 작은 숫자 큰 숫자 구분해줘야 함
        int min = Math.min(a, b);
        int max = Math.max(a, b);
        
        while (true) {
            answer++; //라운드 계산하는 것
            
            //둘의 대진 조건임. 둘이 붙는 숫자가 된다면 while문 탈출
            if (min == max-1 && min % 2 == 1 && max % 2 == 0) break;
            
            //4를 예시로 4번이 이기면 다음 라운드 숫자는 2이고, 7은 4가 된다.
            //그래서 생각한 것이 짝수의 숫자가 이기면 그냥 몫이 되고
            //홀수의 숫자가 이기면 몫에 +1을 해줘야한다.
            min = (min % 2 == 0) ? min / 2 : min / 2 + 1;
            max = (max % 2 == 0) ? max / 2 : max / 2 + 1;
        }
        
        return answer;
    }
}

import java.util.*;
class Solution {
    public int solution(int[][] maps) {
        int row = maps.length;
        int col = maps[0].length;
        boolean[][] check = new boolean[row][col]; //다녀왔는지 체크용
        
        //BFS를 구현하기 위한 큐
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(0, 0, 1));
        
        //상하좌우 움직일 배열
        int[] xMove = {1, -1, 0, 0};
        int[] yMove = {0, 0, -1, 1};
        
        while (!q.isEmpty()) {
            Point p = q.poll();
            int x = p.x;
            int y = p.y;
            int num = p.num;
            
            //만약 x, y가 상대팀 진영이라면 num 리턴하기
            if (x == row - 1 && y == col - 1) return num;
            
            for (int i = 0; i < 4; i++) {
                int xm = x + xMove[i];
                int ym = y + yMove[i];
                
                //움직일 좌표가 범위를 넘진 않았는지, 이미 방문한 좌표인지, 해당 좌표가 벽인지 파악
                if (xm < 0 || ym < 0 || xm >= row || ym >= col) continue;
                if (check[xm][ym] || maps[xm][ym] == 0) continue;
                
                //방문 체크하고 q에 추가하기
                check[xm][ym] = true;
                q.add(new Point(xm, ym, num+1));
            }
        }
        
        //while문을 통과했는데도 리턴되지 않았다면 그냥 -1 리턴
        return -1;
    }
}

class Point {
    int x, y, num;
    public Point(int x, int y, int num) {
        this.x = x;
        this.y = y;
        this.num = num;
    }
}

DFS로 풀면 효율성 테스트에서 시간초과가 나오고, BFS로 풀어야 통과함

class Solution {
    boolean[] check; //다녀갔는지 체크용
    int answer = 0;
    public int solution(int n, int[][] computers) {
        check = new boolean[n];
        
        //아직 방문하지 않은 네트워크는 func함수로 보내기
        for (int i = 0; i < n; i++) {
            if (check[i]) continue;
            answer++; //보낼 때 새로운 네트워크의 시작이라는 뜻으로 answer + 1 하기
            func(n, computers, i);
        }
        return answer;
    }
    
    public void func(int n, int[][] computers, int num){
        for (int i = 0; i < n; i++) {
            if (num == i) continue; //num이랑 i가 같으면 같은 네트워크이기 때문에 pass
            if (check[i]) continue; //check[i]가 true면 방문한 네트워크이기 때문에 pass
            if (computers[num][i] == 0) continue; //computers[num][i]가 0이면 연결되어 있지 않은 네트워크이기 때문에 pass
            check[i] = true; //방문했다고 check[i]는 true로 변경
            func(n, computers, i); 이제 또 i와 연결된 네트워크를 찾기 위해서 함수로 보내기
        }
    }
}​

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        //합계를 구해서 담을 배열
        int[][] sBoard = new int[triangle.length][triangle.length];
        sBoard[0][0] = triangle[0][0];
        
        for (int i = 1; i < triangle.length; i++) {
            만약 3번째 행이면 3번째 열까지만 가면 되기 때문에 범위 설정함
            for (int j = 0; j <= i; j++) {
                sBoard[i][j] = Math.max(sBoard[i][j], sBoard[i-1][j] + triangle[i][j]);
                if (j == 0) continue;
                sBoard[i][j] = Math.max(sBoard[i][j], sBoard[i-1][j-1] + triangle[i][j]);
            }
            
            if (i == triangle.length - 1) {
                for (int j = 0; j <= i; j++) {
                    answer = Math.max(answer, sBoard[i][j]);
                }
            }
        }
        return answer;
    }
}