#유형 : 그래프, 탐색

#난이도 : 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

#유형 : 문자열

#난이도 : lv2

#맨 처음 문제 읽을 때는 너무 어려워 보였는데, 그냥 문자열을 입력받아, 2개씩 끊어 교집합/합집합 을 구하는 것이었다.

입력들을 소문자로 통일해주고, a~z 사이의 값이 아니면 무시하여 부분문자들을 만들어주면 된다.

 

(int)(((double)교집합 / (double)합집합) * 65536) 를 구해주면 된다.

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
package programmers;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
 
public class p17677 {
    static ArrayList<String> inter = new ArrayList<>();
    static ArrayList<String> union = new ArrayList<>();
    static ArrayList<String> arr1 = new ArrayList<>();
    static ArrayList<String> arr2 = new ArrayList<>();
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        System.out.println(solution("aa1+aa2", "AAAA12"));
    }
    public static int solution(String str1, String str2) {
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        for(int i=0; i<str1.length()-1; i++) {
            char ch1 = str1.charAt(i);
            char ch2 = str1.charAt(i+1);
            
            if(ch1 >= 'a' && ch1 <= 'z' && ch2 >= 'a' && ch2 <= 'z') {
                arr1.add(ch1+""+ch2);
            }
        }
        for(int i=0; i<str2.length()-1; i++) {
            char ch1 = str2.charAt(i);
            char ch2 = str2.charAt(i+1);
            
            if(ch1 >= 'a' && ch1 <= 'z' && ch2 >= 'a' && ch2 <= 'z') {
                arr2.add(ch1+""+ch2);
            }
        }
        Collections.sort(arr1);
        Collections.sort(arr2);
        
        
        for(int i=0; i<arr1.size(); i++) {
            String str = arr1.get(i);
            if(arr2.remove(str)) {
                inter.add(str);
            }
            union.add(str);
        }
        for(int i=0; i<arr2.size(); i++) {
            String str = arr2.get(i);
            union.add(str);
        }
        
        double rs = 0;
        if(union.size() == 0)
            rs = 1;
        else
            rs = (double)inter.size() / (double)union.size();
        
        return (int)(rs*65536);
    }
}
 
 cs

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

#프로그래머스_괄호 변환 - Java 자바  (0) 2020.06.02
#프로그래머스_[1차] 캐시 - Java 자바  (0) 2020.05.29
#프로그래머스_문자열 압축 - Java 자바  (0) 2020.05.24
#프로그래머스_길찾기 - Java 자바(2019 KAKAO BLIND RECRUITMENT)  (0) 2020.05.07
#프로그래머스_SQL_String, Date - DATETIME에서 DATE로 형 변환  (0) 2020.04.28

#유형 : 완전탐색, 문자열

#난이도 : 레벨 2

#스택에 넣어서 해결할 수도 있을 것 같은데, 그냥 브루트포스로 풀었다. String 클래스로 +연산하면 비효율적이라 StringBuilder로 풀었는데, 이 방법도 그렇게 효율적으로 보이진 않는다. 각 length를 정해놓고, 그 length 씩만 비교하면 된다. 같은 경우 cnt를 더해주고, 다른 경우 그 전 문자열은 결과에 더해주고, 다른 문자열로 변경하여 다시 비교를 이어가면 된다.

 

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
package programmers;
 
public class p60057 {
    public static void main(String[] args) {
        System.out.println(solution("abcabcabcabcdededededede"));
    }
    
    
    public static int solution(String s) {
        int answer = Integer.MAX_VALUE;
        
        for(int len=1; len<s.length(); len++) {
            StringBuilder rs = new StringBuilder();
            StringBuilder tmp = new StringBuilder();
            StringBuilder current = new StringBuilder();
            int cnt = 1;
            for(int i=0; i<len; i++) {
                tmp.append(s.charAt(i));
            }
            for(int i=len; i<s.length(); i+=len) {
                current = new StringBuilder();
                for(int j=i; j<i+len && j<s.length(); j++) {
                    current.append(s.charAt(j));
                }
                if(tmp.toString().equals(current.toString())) {
                    cnt++;
                }else {
                    if(cnt > 1) {
                        rs.append(cnt);
                        rs.append(tmp);
                    }else {
                        rs.append(tmp);
                    }
                    cnt = 1;
                    tmp = new StringBuilder(current.toString());
                }
            }
            
            if(cnt > 1) {
                rs.append(cnt);
                rs.append(tmp);
            }else {
                rs.append(tmp);
            }
            answer = Math.min(answer, rs.length());
        }
        
        if(answer == Integer.MAX_VALUE)
            answer = 1;
        
        return answer;
    }
}
 
 cs

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

#프로그래머스_[1차] 캐시 - Java 자바  (0) 2020.05.29
#프로그래머스_[1차] 뉴스 클러스터링 - Java 자바  (0) 2020.05.28
#프로그래머스_길찾기 - Java 자바(2019 KAKAO BLIND RECRUITMENT)  (0) 2020.05.07
#프로그래머스_SQL_String, Date - DATETIME에서 DATE로 형 변환  (0) 2020.04.28
#프로그래머스_SQL_String, Date - 오랜 기간 보호한 동물(2)  (0) 2020.04.28

+ Recent posts

티스토리툴바