잡다한 배똥월드

import java.util.*;
class Solution {
    Road[] r; //연결된 길을 모아놓은 Road 자료형 배열
    int[][] times; //연결된 길의 시간을 담은 2차원 배열
    boolean[] check; //방문했는지 체크용 boolean 배열
    ArrayList<Integer> answer; //시간 내에 방문할 수 있는 마을 모아놓은 리턴용 ArrayList
    
    public int solution(int N, int[][] road, int K) {
        answer = new ArrayList<>();
        r = new Road[N];
        times = new int[N][N];
        check = new boolean[N];
        
        //매개변수인 road를 기준으로 r이랑 times 값 채우기
        for (int i = 0; i < road.length; i++) {
            int a = road[i][0] - 1;
            int b = road[i][1] - 1;
            int time = road[i][2];
            
            if (r[a] == null) r[a] = new Road();
            if (r[b] == null) r[b] = new Road();
            
            r[a].addRoad(b);
            r[b].addRoad(a);
            
            //시간은 0을 제외하고서는 작은 값을 넣어야하기 때문에 삼항식으로 작성
            times[a][b] = times[a][b] == 0 ? time : Math.min(times[a][b], time);
            times[b][a] = times[b][a] == 0 ? time : Math.min(times[b][a], time);
        }
        
        check[0] = true;
        func(K, 0, 0);

		//리턴 값은 마을의 수이기 때문에 answer의 길이로 리턴하기
        return answer.size();
    }
    
    public void func(int K, int start, int k) {
        if (k > K) return; //방문에 걸린 시간인 k가 제한 시간인 K보다 작을 경우에는 그냥 리턴
        if (answer.indexOf(start) == -1) answer.add(start); 그 외에는 answer에 마을 번호 추가
        
        ArrayList<Integer> arr = r[start].arr;
        
        if (arr == null) return; //arr가 null이면 방문할 수 있는 마을이 없기 때문에 리턴
        
        for (int i = 0; i < arr.size(); i++) {
            int num = arr.get(i);
            if (check[num]) continue; //방문한 마을이면 다음으로 넘어가고
            check[num] = true; //방문했다고 체크한 후
            func(K, num, k + times[start][num]); //함수 호출
            check[num] = false;
        }
    }
}

class Road {
    ArrayList<Integer> arr;
    public Road() {
        arr = new ArrayList<>();
    }
    
    public void addRoad(int num) {
        if (arr.indexOf(num) == -1) arr.add(num);
    }
}

import java.util.*;

class Solution {

    int[][] times;
    int[] map;
    
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        
        times = new int[N+1][N+1];
        map = new int[N+1];
        
        Arrays.fill(map, Integer.MAX_VALUE);
        
        for (int i = 0; i < road.length; i++){
            int start = road[i][0];
            int end = road[i][1];
            int time = road[i][2];
            
            int temp = times[start][end];
            int temp2 = times[end][start];
            times[start][end] = (temp == 0) ? time : Math.min(temp, time);
            times[end][start] = (temp2 == 0) ? time : Math.min(temp2, time);
        }
        
        int[] arr = new int[N+1];
        Arrays.fill(arr, 1);
        
        funk(1, new int[N+1], 0, arr);
        
        for (int i = 1; i < map.length; i++){
            
            if (map[i] <= K){
                answer++;
            }
        }
        return answer+1;
    }
    
    public void funk(int num, int[] data, int ans, int[] arr){
        
        if (num == data.length){
            return;
        }
        
        if (num == 1){
            data[1] = 1;
            arr[1] = 0;
            funk(num+1, data, ans, arr);
            
            return;
        }
        
        for (int i = 2; i < arr.length; i++){
            int time = times[data[num-1]][i];
            
            if (arr[i] == 0 || time == 0) continue;
            if (map[i] < ans+time) continue;
            
            data[num] = i;
            arr[i] = 0;
           
            map[i] = ans + time;
            funk(num+1, data, ans+time, arr);
            
            arr[i] = 1;
            data[num] = 0;
        }
    }
}

import java.util.*;
class Solution {
    public int[] solution(int[] numbers) {
    	//더한 값들을 담을 배열 선언
        ArrayList<Integer> arr = new ArrayList<>();
        
        //0번부터 number.length-1까지 방문하는 for문
        for (int i = 0; i < numbers.length; i++) {
        	//i번의 다음 순서부터 number.length-1가지 방문하는 for문
            for (int j = i+1; j < numbers.length; j++) {
            
            	//두 숫자를 더한 값이 arr에 없으면 추가하고 아니면 그냥 넘어가기
                int num = numbers[i] + numbers[j];
                if (arr.indexOf(num) == -1) arr.add(num);
            }
        }
        
        //ArrayList 오름차순 정렬
        Collections.sort(arr);
        
        //ArrayList를 int[]로 변환하면서 리턴
        return arr.stream().mapToInt(Integer::intValue).toArray();
    }
}

import java.util.*;
class Solution {
    public int solution(String s) {
        int answer = 0;
        
        //String으로 다루는 것보다 char로 다루는 것이 시간 차지를 덜 하기 때문에
        //s을 char 배열로 만들고 ArrayList에 담기
        char[] c = s.toCharArray();
        ArrayList<Character> arr = new ArrayList<>();
        for (int i = 0; i < c.length; i++) {
            arr.add(c[i]);
        }
        
        //만약 list의 길이가 홀수일 경우에는 올바른 괄호를 만들 수 없기 때문에 그냥 바로 0 리턴
        if (arr.size() % 2 != 0) return 0;
        int bracket = arr.size() / 2;
        
        //한 칸씩 한 칸씩 확인하면서 뒤로 넘기기
        for (int i = 0; i < arr.size(); i++) {
            Stack<Character> stack = new Stack<>();
            int count = 0;
            for (int j = 0; j < arr.size(); j++) {
                char word = arr.get(j);
                
                //만약 닫는 괄호이고,
                if (word == ']' || word == '}' || word == ')') {
                    //스택이 비었다면 탈출
                    if (stack.empty()) break;
                    
                   	//스택 제일 위의 값이 동일한 모양의 열린 모양이 아니라면 탈출
                    if (word == ']' && stack.peek() != '[') break;
                    if (word == '}' && stack.peek() != '{') break;
                    if (word == ')' && stack.peek() != '(') break;
                    
                    stack.pop();
                    count++;
                } else { //단어가 열린 괄호라면 스택에 추가
                    stack.push(word);
                }
            }
            
            //만약에 만들어진 괄호가 만들 수 있는 괄호 숫자와 동일하다면 답+1
            if (count == bracket) answer++;
            
            //맨 앞의 값은 맨 뒤로 추가하고 삭제하기
            arr.add(arr.get(0));
            arr.remove(0);
        }
        return answer;
    }
}

import java.util.*;
class Solution {
    HashMap<String, ArrayList<String>> map;
    ArrayList<String> answer;
    public int solution(String[] user_id, String[] banned_id) {
        map = new HashMap<>(); //banned_id에 해당하는 user_id 검출용
        answer = new ArrayList<>(); //만들 수 있는 banned 리스트 제작용
        
        for (int i = 0; i < banned_id.length; i++) {
        	ArrayList<String> list = map.getOrDefault(banned_id[i], new ArrayList<>());
			//만약 map에서 가져온 배열의 길이가 0이 아니면 이미 체크한 banned_id이기 때문에 continue;            
            if (list.size() != 0) continue;
            
            //user_id와 banned_id[i]를 각각 비교하여 불량 사용자에 해당하는지 파악
            for (int j = 0; j < user_id.length; j++) {
                if (banned_id[i].length() == user_id[j].length()) {
                    boolean value = checkWord(user_id[j], banned_id[i]);
                    if (value) list.add(user_id[j]);
                }
            }
            
            map.put(banned_id[i], list);
        }
        
        create(banned_id, 0, new ArrayList<>());
        return answer.size();
    }
    
    public void create(String[] key, int index, ArrayList<String> result) {
        if (key.length == index) {
           	//이미 만든 리스트인지 확인하기 위해 오름차순 정렬 후 String화해서 확인하기
            Collections.sort(result);
            String word = Arrays.toString(result.toArray());
            if (answer.indexOf(word) == -1) answer.add(word);
            return;
        }
        
        ArrayList<String> value = map.get(key[index]);
        for (int i = 0; i < value.size(); i++) {
            String word = value.get(i);
            if (result.indexOf(word) != -1) continue;
            
            ArrayList<String> temp = new ArrayList<>();
            temp.addAll(result);
            temp.add(word);
            
            create(key, index+1, temp);
        }
    }
    
    public boolean checkWord(String a, String b) {
    	//String배열로 비교하면 시간복잡도가 올라가기 때문에 char배열로 비교
        char[] alist = a.toCharArray();
        char[] blist = b.toCharArray();
        
        for (int i = 0; i < alist.length; i++) {
            if (blist[i] != '*' && alist[i] != blist[i]) {
                return false;
            }
        }
        
        return true;
    }
}

import java.util.*;
class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2]; //리턴할 배열 {시작위치, 끝위치}
        
        //보석 개수와 각 보석의 배열 위치를 지정하기 위해 Map 활용
        HashMap<String, Integer> names = new HashMap<>(); 
        
        //만약 names에 해당 보석에 대한 지정된 위치가 없다면 새로 추가하기
        for (int i = 0; i < gems.length; i++) {
            if (names.getOrDefault(gems[i], 0) == 0) {
                names.put(gems[i], names.size() + 1);
            }
        }
  
        int size = names.size();
        
        //배열 위치 파악하기 위해서
        int[] list = new int[size+1];
        
        //구간 파악을 위해서
        int count = Integer.MAX_VALUE;
        
        for (int i = 0; i < gems.length; i++) {
        	//보석 위치에 대한 배열은 i+1로 수정하기
            list[names.get(gems[i])] = i+1;
            
            boolean value = true;
            //모두 보석이 등장했는지를 파악하기 위한 for문
            for (int j = 1; j <= size; j++) {
                if (list[j] == 0) {
                    value = false;
                    break;
                }
            }
            
            int min = Integer.MAX_VALUE;
            int max = 0;
            
            //모든 보석이 등장했다면 시작 위치와 끝 위치 파악하고,
            //만약 구간 길이가 저장된 count 보다 짧다면 answer 리셋
            if (value) {
                for (int j = 1; j <= size; j++) {
                    min = Math.min(list[j], min);
                    max = Math.max(list[j], max);
                }
                
                if (max - min < count) {
                    answer[0] = min;
                    answer[1] = max;
                    count = max-min;
                }
            }
        }
        
        return answer;
    }
}

import java.util.*;
class Solution {
    public String solution(int n, int k, String[] cmd) {
    	//삭제됬는지 안됬는지를 확인할 배열
        boolean[] list = new boolean[n];
        //처음에는 모두 있기 때문에 true로 설정함
        Arrays.fill(list, true);
        
        //위치 파악을 위한 index 변수 선언
        int index = k;
        
        //삭제된 위치들 모을 stack도 선언
        Stack<Integer> delete = new Stack<>();
        
        //위로든 아래로든 움직이는 것을 선언할 때마다 움직일 필요가 없고
        //삭제나 돌아가기가 호출 될 때 움직임을 모았다가 움직이면 되기 때문에
        //따로 모아놓을 변수 선언
        int moveCount = 0;
        
        
        //cmd 순서대로 돌기 위해서 for문
        for (int i = 0; i < cmd.length; i++) {
        	//cmd[i]를 띄어쓰기 기준으로 나눠서 String 배열 만들기
            String[] s = cmd[i].split(" ");
            //문자 비교를 위해 String으로 하기 보단 char로 하기 위해서 char로 형 변환
            char key = s[0].charAt(0);
            //움직이는 숫자를 파악하기 위해 만약 s가 1보다 길면 숫자 변환하고 아님 0 넣기
            int count = s.length > 1 ? Integer.parseInt(s[1]) : 0;
            
            if (key == 'U') { //만약 U이면 위로 움직여야 하기 때문에 moveCount에선 빼기
                moveCount -= count;
            } else if (key == 'D') { //만약 D이면 아래로 움직여야 하기 때문에 더하기
                moveCount += count;
            } else if (key == 'C') { //C이면
            	//move함수 호출해서 index 위치 움직이기
                index = move(list, index, moveCount);
                //moveCount는 움직였기 때문에 0으로 리셋
                moveCount = 0;
                //현 위치인 index를 삭제해야 하기 때문에 false로 변경
                list[index] = false;
                //삭제된 위치는 스택에 넣기
                delete.push(index);
                //그리고 현 위치에 있으면 안되고 아래로 한 칸 이동해야 하기 때문에 next함수 호출
                index = next(list, index);
            } else if (key == 'Z') { //만약 Z이면
            	//현재 위치 다시 수정하고,
                index = move(list, index, moveCount);
                moveCount = 0;
                //스택에서 제일 마지막에 넣은 값을 꺼내와서
                int reset = delete.pop();
                //해당 위치의 값 다시 true로 변환
                list[reset] = true;
            }
        }
        
        //String으로 붙이면 시간 많이 잡아 먹어서 StringBuilder로 추가한 후 toString()으로 문자열 변환
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.length; i++) {
            if (list[i]) sb.append("O"); else sb.append("X");
        }
        
        return sb.toString();
    }
    
    public int next(boolean[] list, int index) {
    	//일단 아래로 내려가서 삭제되지 않는 값이 있다면 그 위치로 리턴
        for (int i = index+1; i < list.length; i++) {
            if (list[i]) return i;
        }
        
        //아래로 내려가도 리턴되지 않으면 위로 올라가기
        for (int i = index-1; i >= 0; i--) {
            if (list[i]) return i;
        }
        
        return index;
    }
    
    public int move(boolean[] list, int index, int num) {
        if (num > 0) { //만약 num이 0보다 크면 아래로 내려가야하기 때문에
            for (int i = index+1; i < list.length; i++) {
                if (num == 0) break;
                if (list[i]) num--;
                index++;
            }
        } else {
            for (int i = index-1; i >= 0; i--) {
                if (num == 0) break;
                if (list[i]) num++;
                index--;
            }
        }
        
        return index;
    }
}

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;
    }
}