잡다한 배똥월드

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        
        //요청시간 순으로 정렬해놓은 큐
        PriorityQueue<Job> waiting = new PriorityQueue<>(new Comparator<Job>(){
            @Override
            public int compare(Job j1, Job j2) {
                return j1.start - j2.start;
            }
        });
        
        //작업시간 순으로 정렬할 큐
        PriorityQueue<Job> working = new PriorityQueue<>(new Comparator<Job>(){
            @Override
            public int compare(Job j1, Job j2) {
                return j1.work - j2.work;
            }
        });
        
        //waiting에 넣기
        for (int i = 0; i < jobs.length; i++) {
            waiting.offer(new Job(jobs[i][0], jobs[i][1]));
        }
        
        int count = 0; //몇 개 처리됬는지 파악할 변수
        int time = 0; //작업이 끝나는 시간을 담을 변수
        
        while (count < jobs.length) {
        	//waiting이 비어있지 않고, 작업이 끝나는 시간 이전에 요청이 들어온 것이 있다면
            //꺼내서 working에 넣기
        	while (!waiting.isEmpty() && time >= waiting.peek().start) {
                working.offer(waiting.poll());
            }
            
            //만약에 working이 비어있지 않으면
            if (!working.isEmpty()) {
            	//작업시간이 가장 짧은 즉, working 가장 처음에 있는 것을 꺼내서 계산하기
                //time은 작업이 끝나자마자 새로운 작업이 시작되기 때문에 해당 새로운 작업의 작업 시간 추가
                //answer은 총 시간이기 때문에 작업이 완전히 끝나는 시간부터 요청이 들어온 시간을 뺀 값을 추가하기
                //count는 작업 하나가 끝났기 때문에 1 더하기
                Job job = working.poll();
                time += job.work;
                answer += (time - job.start);
                count++;
            } else {
            //working이 비어있으면 time + 1
                time++;
            }
        }
        
        //총 시간에서 jobs의 갯수로 나눠서 리턴
        return answer / jobs.length;
    }
}

class Job {
    int start, work;
    public Job(int start, int work) {
        this.start = start;
        this.work = work;
    }
}

import java.util.*;
class Solution {
    char[][] table;
    HashMap<Character, MatchCard> list;
    public String solution(int m, int n, String[] board) {
        String answer = "";
        table = new char[m][n];
        list = new HashMap<>();
        
        for (int i = 0; i < board.length; i++) {
            table[i] = board[i].toCharArray();
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (table[i][j] == '.' || table[i][j] == '*') continue;
                if (list.get(table[i][j]) != null) continue;
                
                for (int a = 0; a < m; a++) {
                    for (int b = 0; b < n; b++) {
                        if (i == a && j == b) continue;
                        
                        if (table[i][j] == table[a][b]){
                            list.put(table[i][j], new MatchCard(i, j, a, b));
                        }
                    }
                }
            }
        }

        ArrayList<Character> arr = new ArrayList<>();        
        while (list.size() > 0) {
            arr = new ArrayList<>();
            
            for (int i = 0; i < m; i++) {
            }
            for (char key : list.keySet()) {
                MatchCard card = list.get(key);
            
                boolean value = rootCheck(card.x1, card.y1, card.x2, card.y2);
                if (value) {
                    arr.add(key);
                }
                
            }
            
            if (arr.size() == 0) return "IMPOSSIBLE"; 
            
            Collections.sort(arr);
            char key = arr.get(0);
            MatchCard c = list.get(key);
            table[c.x1][c.y1] = '.';
            table[c.x2][c.y2] = '.';
            list.remove(key);
            answer += key;
        }
            
        return answer;
    }
    
    public boolean rootCheck(int x1, int y1, int x2, int y2) {
        if (x1 == x2) {
            if (holCheck(y1, y2, x1)) {return true;} else {return false;}
        }
        if (y1 == y2) {
            if (verCheck(x1, x2, y1)) {return true;} else {return false;}
        }
        
        if (verCheck(x1, x2, y1)) {
            boolean value = false;
            if (x1 < x2) {
                value = holCheck(y1, y2, x2) && cornerCheck(x2, y1);
            } else {
                value = holCheck(y1, y2, x1) && cornerCheck(x1, y1);
            }
            
            if (value) return true;
        }
        
        if (verCheck(x1, x2, y2)) {
            boolean value = false;
            if (x1 < x2) {
                value = holCheck(y1, y2, x1) && cornerCheck(x1, y2);
            } else {
                value = holCheck(y1, y2, x2) && cornerCheck(x2, y2);
            }
            
            if (value) return true;
        }
        
        return false;
    }
    
    public boolean cornerCheck(int x, int y) {
        if (table[x][y] == '.') return true;
        
        return false;
    }
    
    public boolean verCheck(int x1, int x2, int col) {
        if (x1 == x2) return true;
        
        if (x1 < x2) {
            for (int i = x1 + 1; i < x2; i++) {
                if (table[i][col] != '.') return false;
            }
            
        } else {
            for (int i = x1 - 1; i > x2; i--) {
                if (table[i][col] != '.') return false;
            }
        }
        
        return true;
    }
    
    public boolean holCheck(int y1, int y2, int row) {
        if (y1 == y2) return true;
        
        if (y1 < y2) {
            for (int i = y1 + 1; i < y2; i++) {
                if (table[row][i] != '.') return false;
            }
        } else {
            for (int i = y1 - 1; i > y2; i--) {
                if (table[row][i] != '.') return false;
            }
        }
        return true;
    }
}

class MatchCard {
    int x1, x2, y1, y2;
    
    public MatchCard(int x1, int y1, int x2, int y2) {
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
    }
}

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        int position = 0;
        
        Node[] list = new Node[n+1];
        for (int i = 1; i < list.length; i++) {
            list[i] = new Node();
        }
        
        for(int i = 0; i < edge.length; i++) {
            int a = edge[i][0];
            int b = edge[i][1];
            
            Node node1 = list[a];
            Node node2 = list[b];
            
            node1.addNode(b);
            node2.addNode(a);
        }
        
        Queue<Integer> q = new LinkedList<>();
        list[1].far = 0;
        q.add(1);
        while (!q.isEmpty()) {
            int num = q.poll();
            Node node = list[num];
            
            int far = node.far;
            ArrayList<Integer> arr = node.arr;
            
            for (int i = 0; i < arr.size(); i++) {
                int lNum = arr.get(i);
                Node temp = list[lNum];
                if (temp.far != -1) continue;
                
                temp.far = far + 1;
                if (position < far+1) {
                    position = far+1;
                    answer = 1;
                } else if (position == far+1) {
                    answer++;
                }
                
                q.add(lNum);
            }
        }
        
        return answer;
    }
    
    class Node {
        ArrayList<Integer> arr;
        int far = -1;
        public Node() {
            arr = new ArrayList<>();
        }
        
        public void addNode(int num) {
            if (arr == null) arr = new ArrayList<>();
            
            arr.add(num);
        }
    }
}

너비 우선 탐색(BFS)로 탐색했다.

우선 노드 번호와 해당 노드가 연결되어 있는 노드 번호들을 묶기 위해서 Node라는 객체를 정의하였고, 거리는 far로 수정하였다.

그래서 만약에 현재 가장 멀다고 적어놓은 position의 값보다 far이 더 넓다면 해당 far로 answer과 position을 리셋했고, 같다면 answer++를 하였다.

그래프에 대해서 어려운데 이번에는 비교적 잘 푼 것 같다.

그래프 설명 참고

class Solution {
    int answer = Integer.MAX_VALUE;
    public int solution(int N, int number) {
        func(N, number, 0, 0);
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    
    public void func(int N, int number, int count, int prev) {
        int n = N;
        
        if (count > 8) {
            answer = -1;
            return;
        }
        
        if (prev == number) {
            if (answer == -1) {
                answer = count;
            } else {
                answer = Math.min(answer, count);
            }
        }
        
        for (int i = 0; i < 8 - count; i++) {
            func(N, number, count + i + 1, prev + n);
            func(N, number, count + i + 1, prev - n);
            func(N, number, count + i + 1, prev * n);
            func(N, number, count + i + 1, prev / n);
            
            n = (n * 10) + N;
        }
    }
}

머리로는 이해는 되지만 선뜻 코드로 작성하기 어려운 문제.....

일단 for문을 돌리는 이유는

테스트케이스 1번의 N = 5, number = 12일 때를 보면

55 / 5 뭐 이런 식으로 5 하나만 써서 계산하는 것이 아닌 5를 붙여서 55, 555 이런 식으로 숫자를 활용하는 경우가 있어서 for문을 돌려 해당 경우를 돌리기 위해서인데.. 이 부분 때문에 바로 머리 속으로 떠오르지가 않음...

다음에 또 풀어봐야지...