잡다한 배똥월드

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 {
    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

function solution(id_list, report, k) {
    let answer = new Array();
    let list = new Array();
    let count = new Array();
    
	//자바스크립트의 배열의 경우 자료형을 정해놓지 않고 선언하기 때문에 한 번은 값을 넣어줘야 나중에 null이 생기지 않음
    for (let i = 0; i < id_list.length; i++) {
        list[id_list[i]] = new ID(); //유저가 신고한 아이디를 담기 위한 배열
        count[id_list[i]] = 0; //유저의 신고 당한 수를 카운트하기 위한 배열
        answer[i] = 0; //유저가 신고한 아이디가 정지된 개수
    }
    
    for (let i = 0; i < report.length; i++) {
        let s = report[i].split(" "); //띄어쓰기로 구분되어 있기 때문에 split으로 문자열 나누기
        
		//만약 유저가 신고한 적 있는 아이디면 continue
        if (list[s[0]].check(s[1])) continue;
	      
		//없으면 배열에 추가하고 신고 당한 수 +1
        list[s[0]].add(s[1]);
        count[s[1]]++;
    }
    
	//id_list 순서로 해당 유저가 신고한 아이디가 k를 넘었는지 체크
    for (let i = 0; i < id_list.length; i++) {
        let arr = list[id_list[i]].arr;
		    
        for (let j = 0; j < arr.length; j++) {
            if (count[arr[j]] >= k) answer[i]++;
        }
    }
    return answer;
}

//ID라는 객체 생성해서 배열을 만들었음
class ID {
    constructor(){
        this.arr = new Array();
    }
    
    add = function(name) {
        this.arr.push(name);
    }
    
    check = function(name) {
        if (this.arr.indexOf(name) != -1) return true;
        return false;
    }
}

var answer;
function solution(number, k) {
    answer = new Array();
    var num = new Array();
    
    for (let i = 0; i < number.length; i++) {
        num[i] = Number(number.substring(i, i+1));
    }
    
    var start = 0;
    var count = num.length - k;
    
    while (count > 0) {
        start = func(num, start, count);
        count--;
    }
    
    return answer.join('');
}

function func(n, start, count) {
    var max = '0';
    var index = start;
    for (let i = start; i <= n.length - count; i++) {
        if (max < n[i]) {
            max = n[i];
            index = i;
        }
    }
    
    answer.push(max);
    return index + 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);
    }
}

function solution(brown, yellow) {
    for (let i = 1; i <= yellow / i; i++) {
        if (yellow % i != 0) continue;
        
        let num = yellow / i;
        if ((num + 2) * 2 + i * 2 == brown) return [num+2, i+2];
    }
    
    return [0, 0];
}

▽ 자세한 설명이 필요하다면 ▽

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

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

function solution(citations) {
    let answer = 0;
    let size = citations.length;
    
    for (let i = size; i >= 1; i--) {
        let count = 0;
        for (let j = 0; j < size; j++) {
            if (citations[j] >= i) count++;
        }
        
        if (count >= i && size - count <= i) {
            answer = i;
            break;
        }
    }
    return answer;
}

코드 참고용