#유형 : 문자열

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

#유형 : 투 포인터, 탐색, 정렬

#난이도 : 골드 4

# 인덱스를 이동하면서 투포인터 개념을 사용하면 해결할 수 있던 문제.

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class p2473 {
    static int N, idx1, idx2, idx3;
    static int arr[];
    static long minValue = Long.MAX_VALUE;
    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];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        
        solve();
        
        System.out.println(arr[idx1]+" "+arr[idx2]+" "+arr[idx3]);
    }
    private static void solve() {
        // TODO Auto-generated method stub
        for(int i=0; i<N; i++) {
            int j = i+1;
            int k = N-1;
            while(j<k) {
//                System.out.println(arr[i]+" "+arr[j]+" "+arr[k]);
                long sum = arr[i] + arr[j] + arr[k];
                if(Math.abs(sum) < minValue) {
                    idx1 = i;
                    idx2 = j;
                    idx3 = k;
                    minValue = Math.abs(sum);
                }
                //양수를 더해야하므로 j++
                if(sum < 0) {
                    j++;

                }else {
                    k--;
                }
            }
        }
    }
}
 
 cs

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

#백준_1629 곱셈 - Java 자바  (0) 2020.07.01
#백준_2096 내려가기 - Java 자바  (0) 2020.06.27
#백준_1149 RGB거리 - Java 자바  (0) 2020.05.06
#백준_2056 작업 - Java 자바  (0) 2020.05.05
#백준_2407 조합 - Java 자바  (0) 2020.05.04

#유형 : 트리, 자료구조

#난이도 : 프로그래머스 LEVEL 3

#입력을 우선순위큐를 사용하여 Y의 크기순, x는 작은순으로 정렬하면 된다. 우선순위큐를 사용해도 되고, 정렬기준을 통해 정렬을 해도 된다. 그러면 가장 앞에 루트노드가 올것이다. 그다음은 이진트리 조건에 따라 left, right를 정해서 트리를 완성하면 된다. 백준을 주로 풀어와서, 프로그래머스 문제는 좀 출력하기가 어색하다. 따라서 코드가 좀 복잡하게 보일 지라도, 기본 알고리즘은 간단하다

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
package programmers;
 
import java.util.ArrayList;
import java.util.PriorityQueue;
 
public class root {
    static No root;
    static ArrayList<Integer> re[];
    public static void main(String[] args) {
        int nodeinfo[][] = {{5,3},{11,5},{13,3},{3,5},{6,1},{1,3},{8,6},{7,2},{2,2}};
        int [][]answer = solution(nodeinfo);
        for(int i=0; i<2; i++) {
            for(int j=0; j<nodeinfo.length; j++)
                System.out.print(answer[i][j]+" " );
            System.out.println();
        }
    }
    public static int[][] solution(int[][] nodeinfo) {
        solve(nodeinfo);
        int[][] answer = new int[2][nodeinfo.length];
        for(int i=0; i<2; i++) {
                for(int j=0; j<nodeinfo.length; j++) {
                    answer[i][j] = re[i].get(j);
                }
        }
        return answer;
    }
    public static void solve(int[][] nodeinfo) {
//        int[][] answer = {};
        re = new ArrayList[2];
        for(int i=0; i<2; i++) {
                re[i]= new ArrayList<>();
        }
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for(int i=0; i<nodeinfo.length; i++) {
                pq.add(new Node(nodeinfo[i][0], nodeinfo[i][1], i+1));
        }
        
        Node tmp = pq.poll();
        No newNo = new No(tmp.num, tmp.x);
        root = newNo;
        
        while(!pq.isEmpty()) {
                Node nd = pq.poll();
                No n = new No(nd.num, nd.x);
                
                find(root, n);
        }
        preorder(root);
        postorder(root);
    }
    private static void find(No r, No n) {
        // TODO Auto-generated method stub
        if(r.x > n.x && r.left != null) {
            find(r.left, n);
        }else if(r.x > n.x && r.left == null) {
            r.left = n;
        }else if(r.x < n.x && r.right != null) {
            find(r.right, n);
        }else {
            r.right=n;
        }
        
    }
    
    public static void preorder(No n) {
        if(n == null) {
            return;
        }
//        System.out.println(n.num);
        re[0].add(n.num);
        preorder(n.left);
        preorder(n.right);
    }
    public static void postorder(No n) {
        if(n == null)
            return;
        postorder(n.left);
        postorder(n.right);
        re[1].add(n.num);
    }
    
    public static class No{
        int num;
        int x;
        No left;
        No right;
        public No(int n, int x) {
            this.num=n;
            this.x=x;
            this.left=null;
            this.right=null;
        }
    }
    public static class Node implements Comparable<Node>{
        int x;
        int y;
        int num;
        public Node(int x, int y, int num) {
            this.x=x;
            this.y=y;
            this.num=num;
        }
        @Override
        public int compareTo(Node o) {
            // TODO Auto-generated method stub
            if(this.y < o.y)
                return 1;
            else if(this.y == o.y) {
                if(this.x > o.x)
                    return 1;
                else
                    return -1;
            }
            return -1;
        }
    }
}
 
 cs

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

#프로그래머스_[1차] 뉴스 클러스터링 - Java 자바  (0) 2020.05.28
#프로그래머스_문자열 압축 - Java 자바  (0) 2020.05.24
#프로그래머스_SQL_String, Date - DATETIME에서 DATE로 형 변환  (0) 2020.04.28
#프로그래머스_SQL_String, Date - 오랜 기간 보호한 동물(2)  (0) 2020.04.28
#프로그래머스_SQL_String, Date - 중성화 여부 파악하기  (0) 2020.04.28

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

#난이도 : 실버 1

#조건은 다음과 같다

  • 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
  • N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
  • i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

요약하면 인접한 집은 색이 같으면 안된다는 것이다. 아래와 같은 사항을 dp로 풀어내면 된다.

1. 전에 빨강을 칠했다 => 파랑,초록

2. 전에 파랑을 칠했다 => 빨강,초록

3. 전에 초록을 칠했다 => 빨강,파랑 

 

 

dp[i][1]이 빨강색이라고 가정하면, 그 전에는 파랑,초록을 칠해야 한다. 따라서 dp[i-1][2](파랑), dp[i-1][3](초록) 둘 중 한개에서 빨강의 값을 더해주는 것이다.

 

즉 아래와 같이 dp를 풀어내면 된다.

dp[i][1] = Math.min(dp[i-1][2], dp[i-1][3]) + arr[i][1];

dp[i][2] = Math.min(dp[i-1][1], dp[i-1][3]) + arr[i][2];

dp[i][3] = Math.min(dp[i-1][1], dp[i-1][2]) + arr[i][3];

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1149 {
    static int N;
    static int arr[][];
    static int dp[][];
    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][N+1];
        dp = new int[N+1][N+1];
        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());
            }
        }
        // 0 : 빨강, 1 : 파랑, 2 : 초록
        int result = solve();
        
        System.out.println(result);
    }
    private static int solve() {
        // TODO Auto-generated method stub
        // 0 : 빨강, 1 : 파랑, 2 : 초록 
        dp[1][1] = arr[1][1];
        dp[1][2] = arr[1][2];
        dp[1][3] = arr[1][3];
        
        //1번 집의 색은 2번 집의 색과 같지 않아야 한다.
        //N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
        //i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
        // 요약하면 인접한 집은 색이 같으면 안된다는 것 => 1. 전에 빨강을 칠했다 => 파랑,초록 // 2. 전에 파랑을 칠했다 => 빨강,초록 // 3. 전에 초록을 칠했다 => 빨강,파랑 
        for(int i=2; i<=N; i++) {
            dp[i][1] = Math.min(dp[i-1][2], dp[i-1][3]) + arr[i][1];
            dp[i][2] = Math.min(dp[i-1][1], dp[i-1][3]) + arr[i][2];
            dp[i][3] = Math.min(dp[i-1][1], dp[i-1][2]) + arr[i][3];
        }
        int rs = Integer.MAX_VALUE;
        
        for(int i=1; i<=3; i++)
            rs = Math.min(rs, dp[N][i]);
        
        return rs;
    }
}
 
 cs

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

#백준_2096 내려가기 - Java 자바  (0) 2020.06.27
#백준_2473 세 용액 - Java 자바  (0) 2020.05.11
#백준_2056 작업 - Java 자바  (0) 2020.05.05
#백준_2407 조합 - Java 자바  (0) 2020.05.04
#백준_2467 용액 - Java 자바  (0) 2020.05.03

#유형 : 위상 정렬

#난이도 : 골드 4

# 큐를 통해 위상 정렬 알고리즘을 구현하면 되는 문제였다. 위상 정렬 알고리즘이란 싸이클이 허용되지 않는 가정하에 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정하기 위해 사용하는 알고리즘이다. 진입 차수가 0인 노드를 큐에 넣어가며 선행 처리가 끝난(진입 차수가 0이된)노드에서 방문 가능한 노드들을 차례로 방문해주며 시간을 더해주면 된다.

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
71
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p2056 {
    static int N;
    static int cost[], arr[], pre[];
    static ArrayList<Integer> arrList[];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        cost = new int[N+1];
        arr = new int[N+1];
        pre = new int[N+1];
        arrList = new ArrayList[N+1];
        for(int i=0; i<=N; i++)
            arrList[i] = new ArrayList<>();
        for(int i=1; i<=N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            cost[i] = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());
            for(int j=0; j<val; j++) {
                int prev = Integer.parseInt(st.nextToken());
                arrList[prev].add(i);
                pre[i]++;
            }
        }
        
        
        bfs();
        int maxValue = 0;
        for(int i : arr) {
            maxValue = Math.max(maxValue, i);
        }
        System.out.println(maxValue);
    }
    private static void bfs() {
        // TODO Auto-generated method stub
        
        Queue<Integer> queue = new LinkedList<Integer>();
        
        // 진입 차수가 0인 노드를 큐에 넣어준다.
        for(int i=1; i<=N; i++) {
            if(pre[i] == 0) {
                queue.add(i);
                arr[i] = cost[i];
            }
        }
        
        while(!queue.isEmpty()) { 
            int num = queue.poll();
            // 진입 차수가 0 인 노드를 선행으로 갖는 노드들에 대해 수행해준다.
            for(int i=0; i<arrList[num].size(); i++) {
                int next = arrList[num].get(i);
                if(arr[next] < arr[num] + cost[next])
                    arr[next] = arr[num] + cost[next];
                if(--pre[next] == 0) {
                    queue.add(next);
                }
            }
        }
        
    }
}
 
 cs

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

#백준_2473 세 용액 - Java 자바  (0) 2020.05.11
#백준_1149 RGB거리 - Java 자바  (0) 2020.05.06
#백준_2407 조합 - Java 자바  (0) 2020.05.04
#백준_2467 용액 - Java 자바  (0) 2020.05.03
#백준_2166 다각형의 면적 - Java 자바  (0) 2020.05.02

#유형 : 조합, 콤비네이션

#난이도 : 실버 2

# 수학 조합 공식 nCm => n! / (n-m)!m!

# 푸는 방식은 여러가지가 있을텐데, 재귀로 접근했지만 시간초과가 발생하고, long 타입으로도 범위를 받아들일 수 없다. 따라서 BigInteger를 사용하여 문제를 해결하면 된다.

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
 
public class p2407 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n,m;
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        BigInteger num1 = BigInteger.ONE;
        BigInteger num2 = BigInteger.ONE;
        for(int i=0; i<m; i++) {
            num1 = num1.multiply(new BigInteger(String.valueOf(n-i)));
            num2 = num2.multiply(new BigInteger(String.valueOf(i+1)));
        }
        
        System.out.println(num1.divide(num2));
    }
    
    
}    
 
 cs

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

#백준_1149 RGB거리 - Java 자바  (0) 2020.05.06
#백준_2056 작업 - Java 자바  (0) 2020.05.05
#백준_2467 용액 - Java 자바  (0) 2020.05.03
#백준_2166 다각형의 면적 - Java 자바  (0) 2020.05.02
#백준_11758 CCW - Java 자바  (0) 2020.05.01

#유형 : 투포인터 알고리즘

#난이도 : 골드 V

# 단순 반복문을 사용하면 아마도 시간초과가 발생할 것이다. 흔한 투포인터 문제였고, 해당 방식으로 접근하여 해결하였다. 

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
package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class p2467 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N =Integer.parseInt(br.readLine());
        int arr[] = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(arr);
        Point po = null;
        
        int start = 0, end = N-1;
        int val = Integer.MAX_VALUE;
        
 
        while(start < end) {
            
            int v1 = arr[start];
            int v2 = arr[end];
            
            if(Math.abs(v1+v2) < val) {
                val = Math.abs(v1+v2);
                po = new Point(start, end);
            }
            
            if(v1 + v2 < 0)
                start++;
            else
                end--;
        }
        System.out.println(arr[po.x] + " " +arr[po.y]);
    }
}
 
 cs

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

#백준_2056 작업 - Java 자바  (0) 2020.05.05
#백준_2407 조합 - Java 자바  (0) 2020.05.04
#백준_2166 다각형의 면적 - Java 자바  (0) 2020.05.02
#백준_11758 CCW - Java 자바  (0) 2020.05.01
#백준_1916 최소비용 구하기 - Java 자바  (0) 2020.04.30

+ Recent posts

티스토리툴바