아찌방 하우스

https://school.programmers.co.kr/learn/courses/30/lessons/72413

풀이 - 나의 생각

전형적인 다익스트라 알고리즘에다가

비교연산 한 번이 추가 된 문제입니다.

무지와 어파치가 각자의 목적지 'A' 와 'B'에

최소한의 비용으로 가는 방법을 알기 위해서는

결국에 모든 목적지에 최소한의 비용으로 가는 방법을 알아야합니다.

그렇기에

int[] distFromStart = dijkstra(graph, n, s);
int[] distFromA = dijkstra(graph, n, a);
int[] distFromB = dijkstra(graph, n, b);

우선 출발지에서 모든 지점으로의 최소 비용을 구합니다.

A와 B에서 모든 지점의 최소 비용을 구합니다.

그 후 세가지 경우의 합을 비교합니다.

그 이유는

우리가 고려해야하는 경우는

1. 일정 지점까지 동행 후, 그 지점부터 각자의 목적지를 가는 경우

2. 처음부터 각자 가는 경우

두가지 입니다.

출발지에서 시작하는 다익스트라는 일정 지점까지 동행하는 경우를,

A, B에서 출발하는 다익스타는 일정 지점에서부터 각자가 간 경우를 알 수 있게 합니다.

그렇기에 세개의 배열의 합은

목적지까지의 비용을 나타내게 되는겁니다.

코드

import java.util.*;

class Node implements Comparable<Node>{
    int index;
    int cost;
    
    public Node(int index, int cost){
        this.index = index;
        this.cost = cost;
    }
    
    @Override
    public int compareTo(Node other){
        return Integer.compare(this.cost, other.cost);
    }
}

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int[][] graph = new int[n+1][n+1];
        //그래프 초기화 및 값 입력
        for(int i = 1; i <= n; i++){
            Arrays.fill(graph[i], Integer.MAX_VALUE);
        }
        for(int[] fare : fares){
            graph[fare[0]][fare[1]] = fare[2];
            graph[fare[1]][fare[0]] = fare[2];
        }
        
        int[] distFromStart = dijkstra(graph, n, s);
        int[] distFromA = dijkstra(graph, n, a);
        int[] distFromB = dijkstra(graph, n, b);
        
        int minCost = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++){
            if(distFromStart[i] != Integer.MAX_VALUE && distFromA[i] != Integer.MAX_VALUE && distFromB[i] != Integer.MAX_VALUE){
                minCost = Math.min(minCost, distFromStart[i] + distFromA[i] + distFromB[i]);
            }
        }
        
        return minCost;
    }
    
    private int[] dijkstra(int[][] graph, int n, int start){
        int[] dist = new int[n+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        
        while(!pq.isEmpty()){
            Node node = pq.poll();
            int current = node.index;
            int cost = node.cost;
            
            //가야할 곳의 비용이 기존의 비용보다 비싸면 pass
            if(cost > dist[current]) continue;
            
            for(int i = 1; i <= n; i++){
            	//자기 자신의 위치, 연결이 안된 곳은 pass
                if(graph[current][i] == Integer.MAX_VALUE) continue;
                
                int newDist = cost + graph[current][i];
                //새로운 최소 비용일 시 갱신
                if(newDist < dist[i]){
                    dist[i] = newDist;
                    pq.add(new Node(i, newDist));
                }
            }
        }
        
        return dist;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/12916?language=java

풀이 - 나의 생각

String 함수 중 replaceAll을 활용하면 아주 쉽게 해결됩니다.

저 같은 경우 toLowerCase()를 사용했지만

replaceAll("[P,p,Y,y]","") 를 사용하면

P, p, Y, y가 모두 삭제되고

replaceAll("[^P,p,Y,y]","") 를 사용하면

P, p, Y, y를 제외한 문자를 모두 삭제합니다.

아무튼 저는 다 소문자로 바꾸고

p, y을 제외한 문자를 삭제했습니다.

그 후 p를 제외한 문자열 길이와 y를 제외한 문자열 길이가

짝수가 아니면 False를 반환하게 하였습니다.

하지만 이외에도

p를 제외한 문자열과 y를 제외한 문자열의 길이의 차가 0이 아니면

False를 반환하게 해도 됩니다.

코드

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        
        s = s.toLowerCase();
        s = s.replaceAll("[^p,y]","");
        if(s.length() == 0) return answer;
        else if(s.length()%2!=0) return false;
        
        if(s.replaceAll("[p]","").length() == s.replaceAll("[y]","").length()) return true;
        
        return false;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/134240

풀이 - 나의 생각

StringBuilder에 반절분을 저장한 후

"0" 추가 후

기존에 저장된 음식을 뒤집은 걸 append 해주면 됩니다.

String의 경우 reverse 함수가 없지만

StringBuilder에는 reverse 함수가 있기에 이를 활용해 봤습니다.

Stirng으로 하실경우

반복문으로 문자열의 뒤에서부터 하나씩 저장해가면 

reverse된 문자열을 구하실 수 있습니다.

코드

class Solution {
    public String solution(int[] food) {
        StringBuilder sb = new StringBuilder();
        int len = 0;
        for(int i = 1; i < food.length; i++){
            for(int j = 0; j < food[i]/2; j++){
                sb.append(i);
            }
        }
        
        StringBuilder reverse = new StringBuilder(sb).reverse();
        sb.append("0").append(reverse);
        
        return sb.toString();
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/12906

풀이 - 나의 생각

별건 없고

Stack의 맨 위의 숫자가

현재 검사하는 숫자와 같으면 pass

다르다면 Stack에 넣어주면 끝입니다.

코드

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        Stack<Integer> stack = new Stack<>();
        stack.add(arr[0]);
        for(int num : arr){
            if(stack.peek() == num) continue;
            stack.add(num);
        }
        
        int[] answer = new int[stack.size()];
        int index = 0;
        for(int num : stack){
            answer[index++] = num;
        }
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/42583

풀이 - 나의 생각

큐를 트럭과 다리를 담당하도록

2개를 선언했다.

1. Truck Queue

우선 Queue에 truck을 다 집어 넣는다.

2. Bridge Queue

우선 Queue에 다리 길이 만큼 0을 다 집어 넣는다.

이때 0은 truck이 올라가 있지 않다는 것을 의미한다.

3. 반복문 돌리기

while문으로 Bridge Queue가 비어 있지 않는 경우 반복문을 돌린다.

다리에 올라가 있는 트럭의 무게를 체크하면서

다음 트럭을 올려도 되는지, 안 되는지 파악한다.

코드

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0;
        int current_weight = 0;

        Queue<Integer> bridge = new LinkedList<>();
        Queue<Integer> trucks = new LinkedList<>();

        for(int truck : truck_weights){
            trucks.offer(truck);
        }

        for(int i = 0; i < bridge_length; i++){
            bridge.offer(0);
        }
        
        while(!bridge.isEmpty()){
            int passed_truck = bridge.poll();
            current_weight -= passed_truck;
            
            if(!trucks.isEmpty()){
                int next_truck = trucks.peek();
                
                if(current_weight + next_truck <= weight){
                    bridge.offer(trucks.poll());
                    current_weight += next_truck;
                }else{
                    bridge.offer(0);
                }
            }
            
            time++;
        }
        
        return time;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/131704#

풀이 - 나의 생각

원래 레일에는 1번 택배부터 n번 택배까지 순서대로 올라와 있다.

하지만 목적지에 따라

기사가 원하는 순서대로 바꾸기위해서

보조 컨테이너 벨트를(이하 보조 벨트) 사용할 수 있다.

이 보조 벨트에서 짐을 내리는 순서는

올려놓은 순서의 역순으로만 내릴 수 있다.

즉, 4번을 먼저 싣기위해

1, 2, 3 번을 보조 벨트에 올리면

3, 2, 1 순으로 꺼낼 수 있다.

이건 뭐다?

First In, Last Out => Stack 이다.

그래서 이 위의 설명처럼

order[i] 가 원래 짐과 순서가 다르면

그 순서를 맞추기 위해

원하는 짐의 순서(order[i])까지

스택에 넣어주면 된다.

그 후에

스택의 최상위 값(stack.peek())가 원하는 짐이 맞는지 체크만 해주면 된다.

코드

import java.util.*;
class Solution {
    public int solution(int[] order) {
        int answer = 0;
        int len = order.length;
        int box = order[0], num = 0;
        Stack<Integer> subRail = new Stack<>();
                
        for(int i = 0; i < len; i++){
            box = order[i];
            while(num+1 <= box){
                subRail.push(num+1);
                num++;
            }
            
            if(subRail.peek() == box){
                subRail.pop();
                answer++;
            }else break;
        }
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/49993

풀이 - 나의 생각

스킬트리에

유저의 스킬(skill_tree.charAt[i]) 있어?

Yes

-> 순서 맞아?

Yes

skill.charAt[index] == skill_tree.charAt[i]

No

flag = false;

이런식으로 진행하면 됩니다.

코드

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0, index = 0;
        boolean flag = true;
        for(String skill_tree : skill_trees){
            flag = true;
            index = 0;
            for(String sk : skill_tree.split("")){
                if(skill.contains(sk)){
                    if(skill.charAt(index++) != sk.charAt(0)){
                        flag = false;
                        break;
                    }
                }
            }
            
            if(flag) answer++; 
        }
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/12913

풀이 - 나의 생각

dp로 풀어보려고 했는데

그냥 단순히 완탐을 해버렸네요 ㅠㅠ

현재 위치의 값을 가지고

바로 밑에 줄에 있는 값들과 더해 보면서

가장 높은 값만 저장합니다.

그렇게 마지막까지 가면

마지막 줄에는 그 위치에 도달하는 방법 중

가장 높은 값일 경우만 모입니다.

그 후에 마지막 줄에서 최댓값 한 번 찾아주면 됩니다.

ps.

코드 길이를 좀 더 줄이고 싶으면 

dp[0] = Arrays.copyOf(land[0],y);

이렇게 하시면 됩니다.

코드

import java.util.*;
class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int x = land.length, y = land[0].length;
        int[][] dp = new int[x][y];
        dp[0][0] = land[0][0];
        dp[0][1] = land[0][1];
        dp[0][2] = land[0][2];
        dp[0][3] = land[0][3];
        
        for(int i = 0; i < x-1; i++){
            for(int j = 0 ; j < y; j++){
                for(int k = 0; k < y; k++){
                    if(j != k && land[i+1][k] + dp[i][j] > dp[i+1][k]){
                        dp[i+1][k] = land[i+1][k] + dp[i][j];
                    }
                }
            }
        }

        for(int i =0; i < 4; i++){
            answer = Math.max(dp[x-1][i], answer);
        }
        return answer;
    }
}