잡다한 배똥월드

import java.util.*;
class Solution {
    int[][] min, max;
    public int solution(String arr[]) {
        int size = arr.length/2+1;
        min = new int[size][size];
        max = new int[size][size];
        
        int[] list = new int[size];
        
        for (int i = 0; i < arr.length; i+=2) {
            int num = Integer.parseInt(arr[i]);
            if (i == 0) {
                list[i/2] = num;
            } else {
                list[i/2] = arr[i-1].equals("+") ? num : -num;
            }
        }
        
        for (int i = size-1; i >= 0; i--) {
            for (int j = i; j < size; j++) {
                if (i == j) {
                    min[i][j] = list[i];
                    max[i][j] = list[i];
                } else {
                    min[i][j] = Integer.MAX_VALUE;
                    max[i][j] = Integer.MIN_VALUE;
                    
                    for (int k = i; k < j; k++) {
                        boolean value = k == i ? true : false; 
                        func(min[i][k], min[k+1][j], i, j, value);
                        func(min[i][k], max[k+1][j], i, j, value);
                        func(max[i][k], min[k+1][j], i, j, value);
                        func(max[i][k], max[k+1][j], i, j, value);
                    }
                }
            }
        }
        return max[0][size-1];
    }
    
    public void func(int a, int b, int x, int y, boolean value) {
        if (value && a < 0) {
            min[x][y] = Math.min(min[x][y], Math.min(a-b,a+b));
            max[x][y] = Math.max(max[x][y], Math.max(a-b,a+b));
        } else {
            min[x][y] = Math.min(min[x][y], a+b);
            max[x][y] = Math.max(max[x][y], a+b);
        }           
    }
}

테스트 케이스 ① 번으로 예시를 든다면

["1", "-", "3", "+", "5", "-", "8"]를 표로 표시한 것이 아래의 표이다.

노란색으로 칠해진 곳은 해당 위치의 숫자를 넣으면 됨

X자로 채워진 곳은 값 채울 필요 없음

그래서 내부 for문의 범위가 i부터 끝까지 감

     for (int i = size-1; i >= 0; i--) {

          for (int j = i; j < size; j++) {

그리고 뒤에서부터 채우기 때문에 i는 점점 작아지는 식으로 구성

i = 3 일 때 j = 3 일 때 [3][3] = -8

     => [3][3]의 최솟값, 최댓값은 -8

i = 2 일 때 j = 2 일 때 [2][2] = 5 → 그리고 이 때를 기준으로 부호를 체크함

     => [2][2]의 최솟값, 최댓값은 5

j = 3 일 때 [2][3] = [i][j-1] + [i+1][j] = 5 + -8 = -3

     => [2][3]의 최솟값, 최댓값은 -3

※ 기준 부호가 +일 경우에는 계산 시 부호의 변동이 발생하지 않아 최솟값과 최댓값은 동일하게 계산이 됨

i = 1 일 때 j = 1 일 때 [1][1] = -3 → 그리고 이 때를 기준으로 부호를 체크함

     => [1][1]의 최솟값, 최댓값은 -3

j = 2 일 때 [1][2] = [i][j-1] + [i+1][j] = -3 + 5 

     => 기준 부호가 -이므로 두 가지 방식으로 계산이 가능함 -(3+5) 또는 -3+5 

     => [1][2]의 최솟값은 -8, 최댓값은 2

j = 3 일 때 [1][3] = [i][j-2] + [i+1][j], [i][j-1] + [i+2][j]로 계산할 수 있음

     => [i][j-2] + [i+1][j]를 해석하면 [1][1]인 -3과 [2][3]인 (5 - 8)을 계산해서 나온 최솟값/최댓값을 이용하여 구하는 계산식임

          즉, -3 + (5-8) 이기 때문에 -3+(5-8)과 -(3+(5-8))로 계산식을 만들 수 있음

          => 두 계산식으로 구한 값 : -6, 0

     => [i][j-1] + [i+2][j]를 해석하면 [1][2]인 (-3+5)를 계산해서 나온 최솟값/최댓값과 [3][3]인 -8을 이용하여 구하는 계산식임

          즉, (-3+5)-8 이기 때문에 (-3+5)의 최솟값과 최댓값인 -8과 2를 이용하여 (-8)-8과 (2)-8의 계산식을 만들 수 있음

          => 두 계산식으로 구한 값 : -16, -6 => [1][3]의 최솟값 : -16, 최댓값 : 0

※ 기준 부호가 -이지만, 괄호를 활용하여 계산식을 구하는 문제이기 때문에 구분을 해줘야 함.    

     즉, -(3+5)-8과 -3+5-8로 계산을 해야하기 때문에 -8-8이라고 해서 -(8-8)의 계산식으로 만들면 안 됨.

i = 0 일 때 j = 0 일 때 [0][0] = 1 → 그리고 이 때를 기준으로 부호를 체크함

     => [0][0]의 최솟값, 최댓값은 1 j = 1 일 때 [0][1] = [i][j-1] + [i+1][j] = 1 -3

     => [0][1]의 최솟값, 최댓값은 -2

j = 2 일 때 [0][2] = [i][j-2] + [i+1][j], [i][j-1] + [i+2][j]로 계산할 수 있음

     => [i][j-2] + [i+1][j]를 해석하면 [0][0]인 1과 [1][2]인 (-3+5)를 계산해서 나온 최솟값/최댓값을 이용하여 계산식을 만들어야 함

          즉, [1][2]의 최솟값은 -8, 최댓값은 2이므로 (1-8)과 (1+2)의 계산식을 만들 수 있음

          => 두 계산식으로 구한 값 : -7, 3

     => [i][j-1] + [i+2][j]를 해석하면 [0][1]인 (1-3)를 계산해서 나온 최솟값/최댓값과 [2][2]인 5을 이용하여 계산식을 만들어야 함

          즉, [0][1]의 최솟값/최댓값은 -2이므로 (-2)+5의 계산식을 만들 수 있음

          => 계산식으로 구한 값 : 3

j = 3 일 때 [0][3] = [i][j-3] + [i+1][j], [i][j-2] + [i+2][j], [i][j-1] + [i+3][j]로 계산할 수 있음

     => [i][j-3] + [i+1][j]를 해석하면 [0][0]인 1과 [1][3]인 (-3+5-8)을 계산해서 나온 최솟값/최댓값을 이용하여 계산식을 만들어야 함

          즉, [1][3]의 최솟값은 -16, 최댓값은 0이므로 (1) + (-16)과 (1) + (0)의 계산식을 만들 수 있음

          => 두 계산식으로 구한 값 : -15, 1

     => [i][j-2] + [i+2][j]를 해석하면 [0][1]인 (1-3)의 최솟값/최댓값과 [2][3]인 (5-8)를 계산해서 나온 최솟값/최댓값을 이용하여 계산식을 만들어야 함

          즉, [0][1]의 최솟값과 최댓값은 동일하게 -2, [2][2]의 최솟값과 최댓값 역시 동일하게 -3이므로 (-2) + (-3)의 계산식을 만들 수 있음

          => 계산식으로 구한 값 : -5

     => [i][j-1] + [i+3][j]를 해석하면 [0][2]인 (1-3+5)의 최솟값/최댓값과 [3][3]인 -8를 이용하여 계산식을 만들어야 함

          즉, [0][2]의 최솟값과 최댓값은 동일하게 3, [3][3]은 -8이므로 (3) + (-8)의 계산식을 만들 수 있음

          => 계산식으로 구한 값 : -5

               => [0][3]의 최솟값 : -15, 최댓값 : 1

import java.util.*;
class Solution {
	//String으로 문자열 붙이기를 하면 시간을 많이 차지 하기 때문에 일단 StringBuilder로 선언
    StringBuilder answer;
    public String solution(String number, int k) {
        answer = new StringBuilder(); //빈 StringBuilder
        int[] num = new int[number.length()]; //number를 숫자 배열로 담을 배열 선언
        
        //한 자리씩 잘라가면서 int형으로 변환하고, 배열에 담기
        for (int i = 0; i < num.length; i++) {
            num[i] = Integer.parseInt(number.substring(i, i+1));
        }
        
        int count = num.length - k; //만들어야할 숫자 자리 수
        int start = 0;
        
        while (count > 0) { count가 0이 될 때까지 반복하기
            start = func(num, count, start);
            count--;
        }
        
        return answer.toString();
    }
    
    public int func(int[] n, int count, int start) {
        int max = n[start]; 
        int index = start;
        
        start부터 전체 자리 수 - 만들어야할 자리 수의 위치 중 가장 큰 숫자 찾기
        for (int i = start; i <= n.length - count; i++) {
            if (n[i] > max) {
                max = n[i];
                index = i;
            }
        }
        
        //찾으면 answer에 붙이고, index 리턴하기
        answer.append(max);
        return index+1;
    }
}

테스트 케이스 1번인 1924로 코드 풀이를 해보자면

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        
        char[] data = number.toCharArray();
        int k1 = k;
        
        for (int i = 0; i < data.length - 1; i++){
            if (data[i] < data[i+1]){
                for (int j = i; j >= 0; j--){
                    if (data[j] >= data[i+1]){
                        break;
                    }

                    if (k1 == 0) break;
                    
                    if (data[j] != 0 && data[j] < data[i+1]){
                        data[j] = 0;
                        k1--;
                    }
                }
            }
            
            if (k1 == 0) break;
        }
        
        char[] answer = new char[number.length() - k];
        int position = 0;
        
        for (int i = 0; i < data.length; i++){
            if (data[i] != 0){
                answer[position] = data[i];
                position++;
            }
            
            if (position == answer.length) break;
            
        }
        return new String(answer);
    }
}

class Solution {
    public int[] solution(int brown, int yellow) {
        for (int i = 1; i <= yellow / i; i++) {
            if (yellow % i != 0) continue;
            int num = yellow / i;
            if ((num + 2) * 2 + i * 2 == brown) return new int[]{num+2, i+2}; 
        }
        
        return new int[]{0, 0};
    }
}

▽ 자세한 설명이 필요할 땐 ▽

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        int size = citations.length; //n편
        
        for (int i = citations.length; i >= 1; i--) { //h번 카운트용 for문
            int count = 0; //h번 이상 인용된 논문 카운트용
            for (int j = 0; j < citations.length; j++) { //for문으로 확인
                if (citations[j] >= i) count++; //j번 논문이 i번 이상 인용됬다면 count+1
            }
            
            //만약 i번 이상 인용된 논문의 수가 i개 이상이고, 그렇지 않은 논문의 수가 i개 이하면
            if (count >= i && size - count <= i) {
            	//h-index인데, 큰 값에서 줄어들고 있기 때문에 가장 먼저 나온 값이 최대값
                answer = i;
                break;
            }
        }
        return answer;
    }
}

import java.util.*;
class Solution {
    public int[] solution(String[] operations) {
        
        //최소값 기준 우선순위 큐
        PriorityQueue<Integer> minQ = new PriorityQueue<>();
        
        //최대값 기준 우선순위 큐
        PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());
        
        for (int i = 0; i < operations.length; i++) {
            String[] s = operations[i].split(" ");
            if (s[0].equals("I")) { //만약 I면 minQ와 maxQ에 각각 숫자 추가
                int num = Integer.parseInt(s[1]);
                minQ.add(num);
                maxQ.add(num);
            } else { //만약 D면
                if (s[1].equals("1")) { //1일 경우에는 최대값에서 값 지우고
                    maxQ.poll();
                } else { //그렇지 않을 경우에는 최소값에서 값 지우기
                    minQ.poll();
                }
                
                //만약 minQ나 maxQ에 지울 것이 없거나, minQ의 첫번째 값이 maxQ의 첫번째 값보다 클 경우
                if (minQ.size() == 0 || maxQ.size() == 0 || minQ.peek() > maxQ.peek()) {
                	//minQ, maxQ 리셋
                    minQ = new PriorityQueue<>();
                    maxQ = new PriorityQueue<>(Collections.reverseOrder());
                }
            }
        }
        
        //minQ와 maxQ가 비어있다면 0, 0 리턴, 그렇지 않으면 각 최대값, 최소값 리턴
        return minQ.size() == 0 || maxQ.size() == 0 ? new int[]{0, 0} : new int[]{maxQ.peek(), minQ.peek()};
    }
}

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        
        int w = 0; //다리 위에 있는 트럭의 무게
        int time = 0; //걸린 시간
        int position = 0; //지나야할 트럭의 순서를 기록
        
        ArrayList<Integer> bridge = new ArrayList<>(); //다리 위의 모습을 표현할 용도
        int finished = 0; //지난 트럭의 갯수
        
        //다리를 지난 트럭의 수가 총 트럭 수보다 작을 동안만 반복
        while (finished < truck_weights.length) { 
            time++; //시간+1
            
            다리 위에 있는 트럭이 length와 같다면 한 개씩은 앞에서부터 지워줘야 함
            if (bridge.size() == bridge_length) {
                int num = bridge.remove(0); //제일 앞에 있는 트럭 제거
                if (num != -1) { //만약 num이 -1이 아니면 무게가 있는 트럭이라는 뜻이기 때문에
                    w -= num; //다리 위에 있는 트럭의 무게에서 현재 다 지나온 트럭의 무게 빼주고
                    finished++; //통과한 트럭의 개수는 추가
                }
            }
            
            //아직 다리위에 올라가지 않은 트럭이 있고,
            //그 무게가 현재 다리 위에 있는 트럭의 무게와 더해도 감당할 수 있는 무게라면 다리 위로 올림
            if (truck_weights.length > position && w + truck_weights[position] <= weight) {
                w += truck_weights[position];
                bridge.add(truck_weights[position]);
                position++;
            } else { //그렇지 않으면 그냥 빈 칸 추가
                bridge.add(-1);
            }
        }
        
        return time; //마지막에 걸린 시간 리턴하기
    }
}

import java.util.*;
class Solution {
    public int solution(String[][] clothes) {
        HashMap<String, Integer> hash = new HashMap<>();
        
        //곱셈을 해야 해서 1부터 시작
        int answer = 1;
        
        //종류별로 해시에 모으기
      	//이름은 상관 없기 때문에 숫자로 계산
        for (int i = 0; i < clothes.length; i++) {
            hash.put(clothes[i][1], hash.getOrDefault(clothes[i][1], 0) + 1);
        }
        
        //1을 더하는 이유는 해당 옷을 입지 않는 경우를 포함해야 하기 때문임
        for (String key : hash.keySet()) {
            answer *= hash.get(key) + 1;
        }
        
        //모두 착용하지 않는 경우는 제외해야 하기 때문에 1을 빼고 리턴
        return answer - 1;
    }
}

경우의 수 공식만 알면 쉽게 풀 수 있는 문제

class Solution {
    public int solution(int n) {
        int[] list = new int[n+1];
        list[1] = 1;
        list[2] = 2;
        
        for (int i = 3; i <= n; i++) {
            list[i] = (list[i-2] + list[i-1]) % 1000000007;
        }
        return list[n];
    }
}

처음에는 코드를 dfs로 작성했는데 정확성 테스트에서부터 시간 초과가 나왔다.

class Solution {
    int answer;
    public int solution(int n) {
        answer = 0;
        func(n);
        return answer;
    }
    
    public void func(int size) {
        if (size == 0) {
            answer++;
            return;
        }
        
        if (size - 1 >= 0) func(size-1);
        if (size - 2 >= 0) func(size-2);
    }
}

그래서 절대 dfs로 작성하면 안되겠구나 생각을 했는데 이를 통해서 알게 된 점은 아래의 표이다

만약에 가로 길이가 3이면 방법은 길이가 2인 경우와 1인 경우의 방법을 더하는 것이었다.

그래서 동적계획법으로 코드를 짜기 위해 배열을 만들고 그 안에 방법 수를 넣었고,

코드의 내용대로 for문으로 3부터 n번까지 돌렸다.

적어도 이렇게 한다면 n의 최대 길이인 60,000번까지 간다고 해도 반복은 60,000번 밖에 안하는 것이기 때문에

시간 초과도 뜨지 않을 것이라고 확신했다.

근데 점점 숫자가 커지면 int 범위를 넘어갈 것이기 때문에

i-2와 i-1을 더한 값을 문제에서 나누라고 한 1,000,000,007로 나눈 나머지를 넣는 것으로 계산했다.