잡다한 배똥월드

import java.util.*;

class Solution {
    public int[] solution(int N, int[] stages) {
        int[] answer = new int[N];
        int[] arrival = new int[N+1];  //스테이지별 도달한 플레이어 수
        int[] noClear = new int[N+1];  //스테이지별 클리어하지 못한 플레이어 수
        
        //도달한 플레이어 수 구하기
        //stages[j](멈춰있는 스테이지)가 i(스테이지 레벨)보다 크거나 같으면 +1
        for (int i = 1; i <= N; i++) { 
            for (int j = 0; j < stages.length; j++) {
                if (stages[j] >= i) arrival[i]++; 
            }
        }
        
        //도달은 했지만 클리어하지 못한 플레이어 수 구하기
        //stages[i]의 해당 스테이지 +1
        for (int i = 0; i < stages.length; i++) {
            if (stages[i] > N) continue;
            noClear[stages[i]]++;
        }
        
        //해시맵에 스테이지와 해당 스테이지의 실패율 저장
        HashMap<Integer, Double> map = new HashMap<>();
        for (int i = 1; i <= N; i++) {
            if (arrival[i] == 0)
                map.put(i, (double) 0);
            else 
                map.put(i, (double) noClear[i] / arrival[i]);
                
        }
        
       	//실패율(내림차순)로 정렬
        //실패율이 동일하면 스테이지 레벨이 작은 것이 앞으로 오게(오름차순) 정렬
        List<Map.Entry<Integer, Double>> arr = new ArrayList<Map.Entry<Integer, Double>>(map.entrySet());
        Collections.sort(arr, new Comparator<Map.Entry<Integer, Double>>(){
            @Override
            public int compare(Map.Entry<Integer, Double> o1, Map.Entry<Integer, Double> o2) {
                double v1 = o1.getValue();
                double v2 = o2.getValue();
                
                if (v1 < v2) {
                    return 1;
                } else if (v1 == v2) {
                    if (o1.getKey() > o2.getKey()) {
                        return 1;
                    }
                }
                
                return -1;
            }
        });
        
        for (int i = 0; i < arr.size(); i++) {
            answer[i] = arr.get(i).getKey();
        }
        
        return answer;
    }
}

이게 1단계..?

문제를 풀면서 주의해야할 점은 도달한 플레이어 수가 0인 스테이지는 실패율을 0으로 제대로 처리해야 한다

직접 값을 입력하지 않으면 0으로 나누는 것이 되기 때문에 오류가 뜨기 때문이다.

import java.util.*;
class Solution {
    public String solution(String p) {
        return func(p); //func함수 자체가 String을 리턴하기 때문에 바로 리턴
    }
    
    public String func(String word) {
        if (word.equals("")) return ""; //만약 빈 문자열이면 그대로 리턴함
        
        //문자열을 붙이는 작업이 많기 때문에 시간 절약을 위해 StringBuilder 객체 선언하여 활용
        StringBuilder result = new StringBuilder();
        
        int position = 0; //u와 v를 구분하기 위한 위치를 담을 변수
        int count = 0; //균형잡힌 문자열을 알아내기 위해서 사용하는 변수
        String[] s = word.split("");
        
        //올바른 문자열인지 아닌지를 구분하기 위한 변수
        //만약 시작이 "("이면 올바른 문자열이고, 그렇지 않으면 아닌 것
        boolean value = s[0].equals(")") ? false : true; 
        
        for (int i = 0; i < s.length; i++) {
            count += (s[i].equals("(")) ? 1 : -1; //만약 s[i]가 "("면 +1을 아니면 -1을 함
            if (count == 0) { 
            	//괄호의 모양에 따라 +1 또는 -1 하면서 0이 되는 순간이 있음
                //그 순간이 괄호 숫자가 딱 떨어지는 순간이기 때문에 여기서 잘라야 함
                position = i + 1;
                break;
            }
        }
        
        String u = word.substring(0, position);
        String v = word.substring(position, word.length());
        
        if (value) { //올바른 문자열일 때
            result.append(u);
            result.append(func(v));
        } else { //올바른 문자열이 아닐 때
            result.append("(");
            result.append(func(v)); //v는 다시 처음부터 반복해서 리턴해야 하기 때문에 함수 호출
            result.append(")");
            
            char[] uSplit = u.substring(1, u.length()-1).toCharArray(); //앞 뒤 제외하고 배열 만들기
            
            for (int i = 0; i < uSplit.length; i++) { //괄호 뒤집기
                uSplit[i] = uSplit[i] == '(' ? ')' : '(';
            }

            result.append(new String(uSplit));
        }
        
        return result.toString(); //리턴값이 String이기 때문에 toString() 필수
    }
}

문제에서 재귀적으로 수행하라길래 진짜 재귀함수로 풀었음.

import java.util.*;
class Solution {
    HashMap<Integer, HashMap<String, Integer>> map;
    public String[] solution(String[] orders, int[] course) {
        ArrayList<String> answer = new ArrayList<>();
        map = new HashMap<>();
        
        for (int i = 0; i < orders.length; i++) {
            char[] word = orders[i].toCharArray();
            Arrays.sort(word);
            orders[i] = new String(word);
        }
        
        for (int i = 0; i < orders.length; i++) {
            String[] word = orders[i].split("");
            func(word, new StringBuilder(), 0);
        }
        
        for (int i = 0; i < course.length; i++) {
            HashMap<String, Integer> list = map.getOrDefault(course[i], new HashMap<>());
            
            int max = 2;
            ArrayList<String> temp = new ArrayList<>();
            for (String key : list.keySet()) {
                int length = list.get(key);
                if (max < length) {
                    max = length;
                    temp = new ArrayList<>();
                    temp.add(key);
                } else if (max == length) {
                    temp.add(key);
                }
            }
            
            answer.addAll(temp);
        }
        
        Collections.sort(answer);
        return answer.toArray(new String[answer.size()]);
    }
    
    public void func(String[] base, StringBuilder word, int p) {
        HashMap<String, Integer> arr = map.getOrDefault(word.length(), new HashMap<>());
        
        arr.put(word.toString(), arr.getOrDefault(word.toString(), 0) + 1);    
        map.put(word.length(), arr);
            
        if (base.length == word.length()) return;
        
        for (int i = p; i < base.length; i++) {
            StringBuilder sb = new StringBuilder(word);
            sb.append(base[i]);
            
            func(base, sb, i+1);
        }
    }
}

orders의 단어들 일단 오름차순 정렬한다.

정렬한 orders 단어들을 하나씩 꺼내면서 만들 수 있는 단어 리스트를 만들면서 몇 번 만들어지는지를 체크한다

그리고 나서 course를 하나씩 꺼내면서 해당 길이에 대해서 가장 많이 조합된 단어를 answer에 넣는다

마지막으로 answer을 오름차순 정렬한 후 리턴한다.

import java.util.*;

class Solution {
    public int[] solution(int rows, int columns, int[][] queries) {
        int[] answer = new int[queries.length];
        int[][] table = new int[rows][columns];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                table[i][j] = (i * columns) + (j + 1); 
            }
        }
        
        for (int i = 0; i < queries.length; i++) {
            PriorityQueue<Integer> q = new PriorityQueue<>();
            
            int x1 = queries[i][0] - 1;
            int y1 = queries[i][1] - 1;
            int x2 = queries[i][2] - 1;
            int y2 = queries[i][3] - 1;
            
            int fPoint = table[x1][y1];
            
            for (int j = y1+1; j <= y2; j++) {               
                q.add(fPoint);
                int temp = table[x1][j];
                table[x1][j] = fPoint;
                fPoint = temp;
            }
            
            for (int j = x1+1; j <= x2; j++) {               
                q.add(fPoint);
                int temp = table[j][y2];
                table[j][y2] = fPoint;
                fPoint = temp;
            }
            
            for (int j = y2-1; j >= y1; j--) {               
                q.add(fPoint);
                int temp = table[x2][j];
                table[x2][j] = fPoint;
                fPoint = temp;
            }
            
            for (int j = x2-1; j >= x1; j--) {               
                q.add(fPoint);
                int temp = table[j][y1];
                table[j][y1] = fPoint;
                fPoint = temp;
            }
            
            answer[i] = q.poll();
        }
        return answer;
    }
}

우선순위 큐에다가 움직이는 숫자들 넣고 제일 위에 숫자 꺼내면 정렬이나 따로 비교하지 않아도 가장 작은 숫자를 가져올 수 있음

시계방향으로 움직이기 때문에 위쪽 오른쪽 아래쪽 왼쪽으로 이동하는데 이것은 for문으로 처리함.

문제 그대로를 코드로 옮기는 문제라서 어렵진 않았고, 우선순위 큐에 대해서 조금 더 공부하게 됨.

우선 순위 큐 참고 링크

import java.util.*;

class Solution {
    public int solution(String s) {
        char[] word = s.toCharArray();
        Stack<Character> box = new Stack<>();
        
        for (int i = 0; i < word.length; i++) {
            char temp = (!box.isEmpty()) ? box.peek() : ' ';
            if (temp == word[i]) {
                box.pop();
            } else {
                box.push(word[i]);
            }
        }
        
        return (!box.isEmpty()) ? 0 : 1;
    }
}

스택에 한 글자씩 넣으면서 제일 위에 있는 글자와 넣을 단어가 동일하면

넣을 글자는 넣지 않고 넘어가고, 제일 위에 있는 글자는 꺼내서 없앤다.

그렇게 단어를 다 돌 때까지 반복한 후에 마지막에 만약에 스택이 비어있다면 1을 리턴하고 비어있지 않으면 0을 리턴

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        HashMap<Integer, Integer> list = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            list.put(nums[i], list.getOrDefault(nums[i], 0) + 1);
        }
        
        return (nums.length / 2 > list.size()) ? list.size() : nums.length / 2;
    }
}

해시맵으로 폰켓몬 종류가 몇 종류인지 파악하고

종류 수와 nums / 2 중에서 작은 숫자를 리턴하면 되는데, Math.min( )으로 처리하려고 보니까 시간이 조금 더 길어지길래 그냥 삼항연산자로 처리함

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 = 0;
    
    public int solution(int[] numbers, int target) {
        func(numbers, target, 0, 0);
        return answer;
    }
    
    public void func(int[] numbers, int target, int p, int num) {
        if (p == numbers.length) {
            if (target == num) answer++;
            return;
        }
        
        func(numbers, target, p+1, num + numbers[p]);
        func(numbers, target, p+1, num - numbers[p]);
        
    }
}

각 자리의 숫자들의 부호를 구분하는 것이기 때문에 앞에서부터 +냐 -냐 구분하면서 함수 호출