잡다한 배똥월드

import java.util.*;
class Solution {
    public int solution(String begin, String target, String[] words) {
    
    	//words에 target이 있는지 없는지 확인
        boolean value = false;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(target)) {
                value = true;
                break;
            }
        }
        if (!value) return 0;
        
        //words의 단어들을 비교하기 편하게 char배열로 변환 후 ArrayList에 넣기
        ArrayList<char[]> list = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            list.add(words[i].toCharArray());
        }
        
        //target도 한번씩 확인을 해야하기 때문에 미리 char배열로 만들어놓기
        char[] base = target.toCharArray();
        
       	//너비우선탐색인 BFS로 탐색하기 위해서 Queue 선언
        Queue<word> q = new LinkedList<>();
        
        //큐에 begin을 char배열로 변환하여 word 객체로 만들어서 넣기
        q.add(new word(0, begin.toCharArray()));
        
        //q가 비워질 때까지 반복
        while (!q.isEmpty()) {
        	//큐의 제일 상단 값 가져오기
            word w = q.poll();
            char[] temp = w.list;
            int index = w.index;
            
            //temp와 target이 같은지 안같은지 비교. 같으면 해당 index 리턴
            if (check(base, temp) == 0) return index;

			//temp와 list에 있는 단어들 비교
            for (int i = 0; i < list.size(); i++) {
                char[] data = list.get(i);
                //글자가 하나만 다르면 list에서 지우면서 q에 넣기
                if (check(temp, data) == 1) q.add(new word(index+1, list.remove(i)));
            }
        }
        return 0;
    }
    
    //a 글자와 b 글자가 몇 글자 다른지 비교하는 함수
    public int check(char[] a, char[] b) {
        int count = a.length;
        for (int i = 0; i < a.length; i++) {
            if (a[i] == b[i]) count--;
        }
        
        return count;
    }
}

class word {
    int index;
    char[] list;
    public word (int i, char[] list) {
        this.index = i;
        this.list = Arrays.copyOf(list, list.length);
    }
}

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