#유형 : 크루스칼 알고리즘, 그리디

#난이도 : lv3

# 그리디 기반의 크루스칼 알고리즘으로 문제를 해결하였다. 크루스칼 알고리즘을 사용하기 위해서는 싸이클을 체크해야하고(트리에서는 싸이클을 허용하지 않는다.) 이를 위해 union-find 방식을 사용하였다.(간단하게 말하면 어느 집단에 속해있는지, 부모가 누구인지 체크하는것으로 싸이클을 체크하는 데 사용).

 

**크루스칼 알고리즘 순서

1. 입력받은 가중치들을 오름차순으로 정렬한다.

2. 정렬된 순서대로 Edge(u,v)가 다른 집합에 속해있다면, Edge(u,v,val)을 트리에 추가한다.

** 집합을 체크하기 위해 재귀 방식의 find를 사용하고, union을 통해 같은 집합으로 만든다.

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.*;
class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        
        ArrayList<Po> arrList = new ArrayList();
        int arr[] = new int[n+1];
        for(int i=1; i<=n; i++)
            arr[i] = i;
        
        for(int i=0; i<costs.length; i++){
            arrList.add(new Po(costs[i][0], costs[i][1], costs[i][2]));
        }
        Collections.sort(arrList);
        for(int i=0; i<arrList.size(); i++){
 
            Po p = arrList.get(i);
            int x = find(arr, p.u);
            int y = find(arr, p.v);
            if(x != y){
                union(arr, x, y);
                answer += p.val;
            }
        }
        return answer;
    }
    
    public static void union(int arr[], int u, int v){
        int x = find(arr, u);
        int y = find(arr, v);
        
        arr[x] = y;
    }
    
    public static int find(int arr[], int u){
        if(u == arr[u])
            return u;
        else
            return arr[u] = find(arr, arr[u]);
    }
    
    
    public class Po implements Comparable<Po>{
        int u;
        int v;
        int val;
        public Po(int u, int v, int val){
            this.u=u;
            this.v=v;
            this.val=val;
        }
        
        @Override
        public int compareTo(Po o){
            return this.val - o.val;
        }
    }
}
 cs

'프로그래머스' 카테고리의 다른 글

#프로그래머스_오픈채팅방 - Java 자바  (0) 2021.12.08
#프로그래머스_멀쩡한 사각형 - Java 자바  (0) 2021.12.07
#프로그래머스_가장 먼 노드 - Java 자바  (0) 2020.06.25
#프로그래머스_예산 - Java 자바  (0) 2020.06.25
#프로그래머스_큰 수 만들기 - Java 자바  (0) 2020.06.04

#유형 : 다이나믹 프로그래밍

#난이도 : 골드 4

# 다이나믹 프로그래밍의 전형적인 문제로, 현 위치에서 어디로 내려갈 수 있는가를 따지면 된다. 인덱스를 1,2,3 이라고 하였을 때

 

1) 인덱스 1에서는 아래층의 1,2 로 이동할 수 있다 => dp[i][1] = Math.max or min(dp[i-1][1], dp[i-1][2]) + arr[i][1])

2) 인덱스 2에서는 아래층의 1,2,3으로 이동할 수 있다 => dp[i][2] = Math.max or min(dp[i-1][1], dp[i-1][2], dp[i-1][3]) + arr[i][2])

3) 인덱스 3에서는 아래층의 2,3 으로 이동할 수 있다 => dp[i][3] = Math.max or min(dp[i-1][2], dp[i-1][3]) + arr[i][3])

 

이 점화식으로 알고리즘을 짜면 된다. 맨 처음에 생각없이 배열을 [N][N] 사이즈로 했다가 메모리초과가 계속 발생해서 왜 그런지 한참 수정했다.. 2) 를 굳이 줄이자면 min이던, max던 dp[i][1]에서 max 또는 min값을 미리 계산했기 때문에 Math.max or min(dp[i][1] - arr[i][1], dp[i-1][3]) + arr[i][2] 로 나타낼 수 있다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package bj;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p2096 {
    static int N;
    static int arr[][];
    static int max[][], min[][];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1][4];
        max = new int[N+1][4];
        min = new int[N+1][4];
        
        for(int i=1; i<=N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for(int i=1; i<=N; i++) {
            max[i][1] += Math.max(max[i-1][1], max[i-1][2]) + arr[i][1];
            max[i][2] += Math.max(Math.max(max[i-1][1], max[i-1][2]), max[i-1][3]) + arr[i][2];
            max[i][3] += Math.max(max[i-1][2], max[i-1][3]) + arr[i][3];
            
            min[i][1] += Math.min(min[i-1][1], min[i-1][2]) + arr[i][1];
            min[i][2] += Math.min(Math.min(min[i-1][1], min[i-1][2]), min[i-1][3]) + arr[i][2];
            min[i][3] += Math.min(min[i-1][2], min[i-1][3]) + arr[i][3];
        }
        
        int maxValue = 0, minValue = Integer.MAX_VALUE;
        for(int i=1; i<=3; i++) {
            maxValue = Math.max(maxValue, max[N][i]);
            minValue = Math.min(minValue, min[N][i]);
        }
        
        System.out.println(maxValue+" " +minValue);
    }
}
 cs

'백준' 카테고리의 다른 글

#백준_10828 스택 - Java 자바  (0) 2020.07.06
#백준_1629 곱셈 - Java 자바  (0) 2020.07.01
#백준_2473 세 용액 - Java 자바  (0) 2020.05.11
#백준_1149 RGB거리 - Java 자바  (0) 2020.05.06
#백준_2056 작업 - Java 자바  (0) 2020.05.05

#유형 : 그래프, 탐색

#난이도 : LV3

# BFS로 접근하여 풀었다. 입력받은 배열을 boolean 배열로 양방향으로 변환하였고, 1번에서 가장 먼 노드이니까 큐에 1을 넣고 연결확인하면서 반복문을 돌리면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.*;
class Solution {
    public int solution(int n, int[][] edge) {
        
        
        int dist[] = new int[n+1];
        boolean visit[][] = new boolean[n+1][n+1];
        for(int i=0; i<edge.length; i++){
            visit[edge[i][0]][edge[i][1]] = true;
            visit[edge[i][1]][edge[i][0]] = true;
        }
        
        Queue<Integer> queue = new LinkedList();
        queue.add(1);
        int max = 0;
        
        while(!queue.isEmpty()){
            int idx = queue.poll();
            for(int j=2; j<=n; j++){
                if(dist[j] == 0 && visit[idx][j]){
                    dist[j] = dist[idx] + 1;
                    queue.add(j);
                }
            }
        }
        for(int i=0; i<n+1; i++){
            max = Math.max(max, dist[i]);
        }
        int cnt = 0;
        for(int i=0; i<n+1; i++){
            if(max == dist[i])
                cnt++;
        }
        
        return cnt;
    }
}
 cs

'프로그래머스' 카테고리의 다른 글

#프로그래머스_멀쩡한 사각형 - Java 자바  (0) 2021.12.07
#프로그래머스_섬 연결하기 - Java 자바  (0) 2020.06.28
#프로그래머스_예산 - Java 자바  (0) 2020.06.25
#프로그래머스_큰 수 만들기 - Java 자바  (0) 2020.06.04
#프로그래머스_다리를 지나는 트럭 - Java 자바  (0) 2020.06.04

#유형 : 이분탐색

#난이도 : LV3

#이분탐색의 기본적인 문제로써, 주어진 배열을 정렬하여 오름차순으로 만들어 주는 아이디어까지 생각했다면 다 풀었다고 생각해도 된다. 이후에는 정석적인 이분탐색으로 코딩하여 해결하면 됨

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.*;
class Solution {
    public int solution(int[] budgets, int M) {
        int answer = 0;
        
        Arrays.sort(budgets);
        
        long sum = 0;
        for(int i=0; i<budgets.length; i++){
            sum += budgets[i];
        }
        if(sum < M)
            return budgets[budgets.length-1];
        
        int min = M / budgets.length;
        int max = budgets[budgets.length-1];
        int middle = 0;
        int stand = 0; 
        while(true){
            middle = (min+max)/2;
            sum = 0;
            
            for(int i=0; i<budgets.length; i++){
                if(budgets[i] > middle)
                    sum += middle;
                else
                    sum += budgets[i];
            }
            if(stand == middle)
            {
                answer = middle;
                break;
            }
            if(sum > M){
                max = middle;
            }else{
                min = middle;
            }
            stand = middle;
        }
        return answer;
    }
 
}
 cs

'프로그래머스' 카테고리의 다른 글

#프로그래머스_섬 연결하기 - Java 자바  (0) 2020.06.28
#프로그래머스_가장 먼 노드 - Java 자바  (0) 2020.06.25
#프로그래머스_큰 수 만들기 - Java 자바  (0) 2020.06.04
#프로그래머스_다리를 지나는 트럭 - Java 자바  (0) 2020.06.04
#프로그래머스_괄호 변환 - Java 자바  (0) 2020.06.02

#유형 : 그리디

#난이도 : lv2 

# 1000000까지 숫자 + 1000000개의 숫자를 뺄 수 있으므로  완전탐색으로 접근하면 시간초과가 발생한다. 그리디로 접근해야한다.

 

#만약 리턴해야하는 값이 4자리의 수라면, 입력값에서 맨뒤의 3자리를 제외한 문자열 부분에서 가장 큰 수를 찾는다. 그리고나서 큰 수를 찾은 자리 이후 부터 마지막 2자리를 제외한 곳에서 큰값을 찾는다. 이 과정을 반복하면 된다. 

ex) 5678543 => 5,6,7,8중 가장 큰 수 8 

 

 

 

Ex) 23563850135 에서 4자리 => 맨 뒤 1,3,5를 제외한 숫자중에 가장 큰 수를 찾는다. 23563850 ==> 8이다.

answer = "8" 오른쪽부터 다시 탐색을 한다. 50135중에 맨뒤 2개를 제외하고 가장 큰 값을 찾는다. 5이다. answer = "85"

0135 중 맨뒤 5를 제외하고 0,1,3 중에 가장 큰 값을 찾는다 => 3 ==> answer = "853" 맨뒤 5를 붙이면 Answer = "8535"가 된다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public String solution(String number, int k) {
        StringBuilder answer = new StringBuilder();
        
        int idx = 0;
        int comp = 0;
        for(int i=0; i<number.length()-k; i++){
            comp = 0;
            for(int j=idx; j<=i+k; j++){
                if(comp < number.charAt(j)-'0'){
                    comp = number.charAt(j)-'0';
                    idx = j+1;
                }
            }
            answer.append(comp);
        }
        return answer.toString();
    }
 cs

'프로그래머스' 카테고리의 다른 글

#프로그래머스_가장 먼 노드 - Java 자바  (0) 2020.06.25
#프로그래머스_예산 - Java 자바  (0) 2020.06.25
#프로그래머스_다리를 지나는 트럭 - Java 자바  (0) 2020.06.04
#프로그래머스_괄호 변환 - Java 자바  (0) 2020.06.02
#프로그래머스_[1차] 캐시 - Java 자바  (0) 2020.05.29

#유형 : 스택/큐

#난이도 : lv2

# 다리에 올라온 트럭을 먼저 처리하고, 그 다음 트럭을 올려보내는 순서로 구현하면 된다. 다음 트럭을 올릴 때는 현재 다리의 총 중량과 다음 트럭의 합을 중량한계값과 비교하면 된다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0;
        
        Queue<Integer> wait = new LinkedList();
        Queue<Point> bridge = new LinkedList();
        for(int i=0; i<truck_weights.length; i++)
            wait.add(truck_weights[i]);
        
        int total=0;
        while(!wait.isEmpty() || !bridge.isEmpty()){
            time++;
            if(!bridge.isEmpty()){
                Point p = bridge.peek();
                if(time - p.y >= bridge_length){
                    total -= p.x;
                    bridge.poll();
                }
            }
            
            if(!wait.isEmpty()){
                if(total + wait.peek() <= weight){
                    int tmp = wait.poll();
                    total += tmp;
                    
                    bridge.offer(new Point(tmp, time));
                }
            }
        }
        
        return time;
    }
 cs

'프로그래머스' 카테고리의 다른 글

#프로그래머스_예산 - Java 자바  (0) 2020.06.25
#프로그래머스_큰 수 만들기 - Java 자바  (0) 2020.06.04
#프로그래머스_괄호 변환 - Java 자바  (0) 2020.06.02
#프로그래머스_[1차] 캐시 - Java 자바  (0) 2020.05.29
#프로그래머스_[1차] 뉴스 클러스터링 - Java 자바  (0) 2020.05.28

#유형 : 시뮬레이션, 문자열 처리

#난이도 : lv2

#주어진 조건대로 구현하면 되는데, 뒤집는다는 부분을 StringBuffer.reverse() 를 썼는데, 문자열을 뒤집는 것이 아니고 ( -> ) / ( -> ) 로 바꾸는 것이기 때문에 12번? 조건부터 틀렸었다. 이 점만 주의하면 될 듯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.util.*;
class Solution {
    public String solution(String p) {
        String answer = "";
        answer = solve(p);
        return answer;
    }
    public static String solve(String p){
        if(p.length() == 0)
            return "";
        
        int idx = divide(p);
        
        String u = p.substring(0, idx);
        String v = p.substring(idx, p.length());
        
        if(check(u)){
            return u + solve(v);
        }else{
            String tmp = '(' + solve(v) + ')';
            u = u.substring(1, u.length()-1);
            
            
            u = reverse(u);
            return tmp + u;
        }
    }
    public static String reverse(String str){
        String tmp = "";
        for(int i=0; i<str.length(); i++){
            if(str.charAt(i) == '(')
                tmp += ')';
            else
                tmp += '(';
        }
        return tmp;
    }
    public static int divide(String str){
        int num1 = 0, num2 = 0;
        int idx = 0;
        for(; idx<str.length(); idx++){
            if(str.charAt(idx) == '(')
                num1++;
            else
                num2++;
            
            if(num1 == num2)
                return idx+1;
            
        }
        return idx;
    }
    public static boolean check(String str){
        Stack<Character> st = new Stack();
        for(int i=0; i<str.length(); i++){
 
            if(str.charAt(i) == '(')
                st.push(str.charAt(i));
            else{
                if(st.isEmpty())
                    return false;
                else if(st.pop() != '(')
                    return false;
            }
        
        }
        
        return true;
    }
}
 cs

'프로그래머스' 카테고리의 다른 글

#프로그래머스_큰 수 만들기 - Java 자바  (0) 2020.06.04
#프로그래머스_다리를 지나는 트럭 - Java 자바  (0) 2020.06.04
#프로그래머스_[1차] 캐시 - Java 자바  (0) 2020.05.29
#프로그래머스_[1차] 뉴스 클러스터링 - Java 자바  (0) 2020.05.28
#프로그래머스_문자열 압축 - Java 자바  (0) 2020.05.24

#유형 : 구현, 문자열

#난이도 : lv2

# 카카오 기출들은 문제 설명이 어려워 보이지만, 풀어보면 기대만큼 어렵지 않다. 

# 배열리스트에 조건을 따져가며 구현하였다. LRU를 구현해주기 위해, 똑같은 입력이 들어올 때, 해당 문자열을 배열에서 제거하고 맨 뒤에 다시 추가해주면서 구하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.*;
 
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        ArrayList<String> arrList = new ArrayList();
        
        if(cacheSize == 0){
            answer = cities.length * 5;
        }else{
            String tmp = cities[0].toLowerCase();
            arrList.add(tmp);
            answer += 5;
            for(int i=1; i<cities.length; i++){
                tmp = cities[i].toLowerCase();
                if(arrList.contains(tmp)){
                    arrList.remove(tmp);
                    arrList.add(tmp);
                    answer += 1;
                }else{
                    if(arrList.size() == cacheSize){
                        arrList.remove(0);
                        arrList.add(tmp);
                        answer += 5;
                    }else{
                        arrList.add(tmp);
                        answer += 5;
                    }
                }
            }
        }
        
        
        
        
        return answer;
    }
}
 cs

'프로그래머스' 카테고리의 다른 글

#프로그래머스_다리를 지나는 트럭 - Java 자바  (0) 2020.06.04
#프로그래머스_괄호 변환 - Java 자바  (0) 2020.06.02
#프로그래머스_[1차] 뉴스 클러스터링 - Java 자바  (0) 2020.05.28
#프로그래머스_문자열 압축 - Java 자바  (0) 2020.05.24
#프로그래머스_길찾기 - Java 자바(2019 KAKAO BLIND RECRUITMENT)  (0) 2020.05.07

+ Recent posts

티스토리툴바