잡다한 배똥월드

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; //마지막에 걸린 시간 리턴하기
    }
}

function solution(clothes) {
    var answer = 1;
    let hash = new Array();
    
    for (var i = 0; i < clothes.length; i++) {
        if (hash[clothes[i][1]] == null) hash[clothes[i][1]] = 0;
        hash[clothes[i][1]]++;
    }
    
    for (let key in hash) {
        answer *= hash[key] + 1;
    }
    return answer - 1;
}

자세한 설명은 자바 코드에서 확인 가능!

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

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

function solution(n) {
    let list = new Array();
    list[1] = 1;
    list[2] = 2;
    
    for (var i = 3; i <= n; i++) {
        list[i] = (list[i-1] + list[i-2]) % 1000000007;
    }
    
    return list[n];
}

자세한 설명은 자바 코드에 작성되어 있음

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로 나눈 나머지를 넣는 것으로 계산했다.

자바에서는 객체를 만들려면 보통 class를 이용하여 새로운 객체를 생성한다.

근데 자바 스크립트에서는 object 객체를 더 많이 쓰는 것 같았음.

내가 배운 것도 Object 객체 뿐이었고...

그래서 바로 인터넷 검색

Object 객체의 경우에는

const people = {
	name: 이름,
    	age: 나이
}

뭐 이런 식으로 값을 딱 넣어놓고 선언을 해야하기 때문에 재사용이 어려움

그래서 자바에서 people 자료형의 배열을 만들기 위해서는 각각 생성을 달리 해야 함.

Constructor 생성자는 자바와 마찬가지로 class를 이용하는 것임

class people {
     constructor() {
    	//초기화하는 부분
    }
    
    const 함수명 = function(이름, 나이) {
         this.name = 이름;
         this.age = 나이;
    }
}

이런 식으로 만들어 놓으면 재사용할 수 있게 됨

단, 자바의 경우에는 자료형을 정해놓고 배열을 생성하지만

class people {
	String name;
    int age;
	public people(String n, int a) {
         this.name = n;
         this.a;
    }
}

class Main {
	public void main() {
         people[] p = new people[5];
    }
}

자바 스크립트의 경우에는 그냥 배열로 선언한 후에 그냥 추가하면 됨

class people {
     constructor(이름, 나이){
     	this.name = 이름;
        this.age = 나이;
     }
}

function main() {
	let p = new Array();
}

여하튼 자바스크립트는 자바랑 비슷한듯 하지만 어렵다.....

자바 코드에 설명이 적혀 있어서 참고 하면서 보면 됩니다~

function solution(N, road, K) {
    let answer = new Array();
    let r = new Array(N);
    let times = new Array(N);
    let check = new Array(N);
    for (var i = 0; i < times.length; i++) {
        times[i] = new Array(N);
        check[i] = false;
    }

    for (var i = 0; i < road.length; i++) {
        var a = road[i][0] - 1;
        var b = road[i][1] - 1;
        var time = road[i][2];
        
        if (r[a] == null) r[a] = new Road();
        if (r[b] == null) r[b] = new Road();
        
        r[a].addRoad(b);
        r[b].addRoad(a);
        times[a][b] = times[a][b] == null ? time : Math.min(times[a][b], time);
        times[b][a] = times[b][a] == null ? time : Math.min(times[b][a], time);
    }
    
    const func = function(K, start, k) {
        if (K < k) return;
        if (answer.indexOf(start) == -1) answer.push(start);
        
        let arr = r[start].arr;
        for (var i = 0; i < arr.length; i++) {
            var num = arr[i];
            if (check[num]) continue;
            check[num] = true;
            func(K, num, k + times[start][num]);
            check[num] = false;
        }
    }
        
    check[0] = true;
    func(K, 0, 0);

    return answer.length;
}

class Road {
    constructor() {
        this.arr = new Array();
    }

    addRoad(num) {
        if (this.arr.indexOf(num) == -1) this.arr.push(num);
    }
}

import java.util.*;
class Solution {
    Road[] r; //연결된 길을 모아놓은 Road 자료형 배열
    int[][] times; //연결된 길의 시간을 담은 2차원 배열
    boolean[] check; //방문했는지 체크용 boolean 배열
    ArrayList<Integer> answer; //시간 내에 방문할 수 있는 마을 모아놓은 리턴용 ArrayList
    
    public int solution(int N, int[][] road, int K) {
        answer = new ArrayList<>();
        r = new Road[N];
        times = new int[N][N];
        check = new boolean[N];
        
        //매개변수인 road를 기준으로 r이랑 times 값 채우기
        for (int i = 0; i < road.length; i++) {
            int a = road[i][0] - 1;
            int b = road[i][1] - 1;
            int time = road[i][2];
            
            if (r[a] == null) r[a] = new Road();
            if (r[b] == null) r[b] = new Road();
            
            r[a].addRoad(b);
            r[b].addRoad(a);
            
            //시간은 0을 제외하고서는 작은 값을 넣어야하기 때문에 삼항식으로 작성
            times[a][b] = times[a][b] == 0 ? time : Math.min(times[a][b], time);
            times[b][a] = times[b][a] == 0 ? time : Math.min(times[b][a], time);
        }
        
        check[0] = true;
        func(K, 0, 0);

		//리턴 값은 마을의 수이기 때문에 answer의 길이로 리턴하기
        return answer.size();
    }
    
    public void func(int K, int start, int k) {
        if (k > K) return; //방문에 걸린 시간인 k가 제한 시간인 K보다 작을 경우에는 그냥 리턴
        if (answer.indexOf(start) == -1) answer.add(start); 그 외에는 answer에 마을 번호 추가
        
        ArrayList<Integer> arr = r[start].arr;
        
        if (arr == null) return; //arr가 null이면 방문할 수 있는 마을이 없기 때문에 리턴
        
        for (int i = 0; i < arr.size(); i++) {
            int num = arr.get(i);
            if (check[num]) continue; //방문한 마을이면 다음으로 넘어가고
            check[num] = true; //방문했다고 체크한 후
            func(K, num, k + times[start][num]); //함수 호출
            check[num] = false;
        }
    }
}

class Road {
    ArrayList<Integer> arr;
    public Road() {
        arr = new ArrayList<>();
    }
    
    public void addRoad(int num) {
        if (arr.indexOf(num) == -1) arr.add(num);
    }
}

import java.util.*;

class Solution {

    int[][] times;
    int[] map;
    
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        
        times = new int[N+1][N+1];
        map = new int[N+1];
        
        Arrays.fill(map, Integer.MAX_VALUE);
        
        for (int i = 0; i < road.length; i++){
            int start = road[i][0];
            int end = road[i][1];
            int time = road[i][2];
            
            int temp = times[start][end];
            int temp2 = times[end][start];
            times[start][end] = (temp == 0) ? time : Math.min(temp, time);
            times[end][start] = (temp2 == 0) ? time : Math.min(temp2, time);
        }
        
        int[] arr = new int[N+1];
        Arrays.fill(arr, 1);
        
        funk(1, new int[N+1], 0, arr);
        
        for (int i = 1; i < map.length; i++){
            
            if (map[i] <= K){
                answer++;
            }
        }
        return answer+1;
    }
    
    public void funk(int num, int[] data, int ans, int[] arr){
        
        if (num == data.length){
            return;
        }
        
        if (num == 1){
            data[1] = 1;
            arr[1] = 0;
            funk(num+1, data, ans, arr);
            
            return;
        }
        
        for (int i = 2; i < arr.length; i++){
            int time = times[data[num-1]][i];
            
            if (arr[i] == 0 || time == 0) continue;
            if (map[i] < ans+time) continue;
            
            data[num] = i;
            arr[i] = 0;
           
            map[i] = ans + time;
            funk(num+1, data, ans+time, arr);
            
            arr[i] = 1;
            data[num] = 0;
        }
    }
}