[프로그래머스] Lv3 문제풀이1(feat. JAVA)

정수 삼각형 - Dynamic Programming

import java.io.*;
import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;

        int[][] dp = new int[triangle.length][triangle[triangle.length-1].length];

        dp[0][0] = triangle[0][0];

        for(int i = 1; i < triangle.length; i++) {
            for(int j = 0; j < i + 1; j++) {
                if(j == 0) {
                    dp[i][j] = dp[i-1][j] + triangle[i][j];
                } else if (j == i) {
                    dp[i][j] = dp[i-1][j-1] + triangle[i][j];
                } else {
                    dp[i][j] = triangle[i][j] + Math.max(dp[i-1][j], dp[i-1][j-1]);
                }
            }
        }

        answer = Arrays.stream(dp[dp.length-1]).max().getAsInt();

        return answer;
    }
}

 

 

이중 우선순위 큐 - Heap

import java.io.*;
import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {0, 0};

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        PriorityQueue<Integer> clone = new PriorityQueue<>();

        StringTokenizer str;
        for(String oper : operations) {
            str = new StringTokenizer(oper);

            switch (str.nextToken()) {
                case "I" : {
                    queue.offer(Integer.parseInt(str.nextToken()));
                    break;
                }
                case "D" : {
                    int sort = Integer.parseInt(str.nextToken());
                    if(sort == 1) {
                        if (!queue.isEmpty()) {
                            queue.stream()
                                    .limit(queue.size() - 1)
                                    .forEach(clone::offer);
                            queue.clear();
                            clone.forEach(queue::offer);
                            clone.clear();
                        }
                    }
                    else {
                        if (!queue.isEmpty())
                            queue.poll();
                    }
                    break;
                }
            }
        }

        if(queue.isEmpty())
            return answer;

        answer[1] = queue.peek();
        while(queue.size() != 1)
                queue.poll();
        answer[0] = queue.peek();
        return answer;
    }
}

 

 

네트워크 - DFS/BFS

import java.io.*;
import java.util.*;

class Solution {
    public static int[] parent = new int[200];

    public boolean union(int a, int b) {
        a = find(a);
        b = find(b);

        if(a == b)
            return false;

        if(a < b)
            parent[b] = a;
        else
            parent[a] = b;

        return true;
    }

    public int find(int a) {
        if(a == parent[a]) return a;
        return find(parent[a]);
    }
    public int solution(int n, int[][] computers) {
        int answer = 0;

        for(int i = 0; i < parent.length; i++)
            parent[i] = i;

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i == j) continue;

                if(computers[i][j] == 1){
                    union(i, j);
                }
            }
        }

        ArrayList<Integer> plist = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            int parent = find(i);
            if(!plist.contains(parent)){
                plist.add(parent);
            }
        }
        answer = plist.size();
        return answer;
    }
}