Skip to content

Commit 0c4a3db

Browse files
GoogleokGoogleok
committed
27주차 알고리즘 완료 > (컬러링북, 후보키는 못 풀어서 다른 코드 참고)
1 parent d677dc5 commit 0c4a3db

4 files changed

Lines changed: 198 additions & 2 deletions

File tree

‎src/programmers/level2/week_14/solution003/Solution003.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -9,8 +9,8 @@
99
public class Solution003 {
1010
public static void main(String[] args) {
1111
Solution003 sol = new Solution003();
12-
int[] A = { 1, 4, 2 };
13-
int[] B = { 5, 4, 4 };
12+
int[] A = {1, 4, 2};
13+
int[] B = {5, 4, 4};
1414
System.out.println(sol.solution(A, B));
1515
}
1616

‎src/programmers/level2/week_27/Solution001.java‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package programmers.level2.week_27;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* 카카오프렌즈 컬러링북
7+
* https://programmers.co.kr/learn/courses/30/lessons/1829?language=java
8+
*/
9+
public class Solution001 {
10+
int area = 0;
11+
int attrPicture[][];
12+
boolean check[][];
13+
14+
public static void main(String[] args) {
15+
int m = 6;
16+
int n = 4;
17+
int[][] picture = {{1, 1, 1, 0}, {1, 2, 2, 0}, {1, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 3}};
18+
Solution001 sol = new Solution001();
19+
System.out.println(Arrays.toString(sol.solution(m, n, picture)));
20+
}
21+
22+
public int[] solution(int m, int n, int[][] picture) {
23+
int numberOfArea = 0;
24+
int maxSizeOfOneArea = 0;
25+
attrPicture = picture;
26+
check = new boolean[m][n];
27+
for (int row = 0; row < m; row++) {
28+
for (int col = 0; col < n; col++) {
29+
if (picture[row][col] == 0 || check[row][col])
30+
continue;
31+
numberOfArea += 1;
32+
getArea(row, col);
33+
if (maxSizeOfOneArea < area)
34+
maxSizeOfOneArea = area;
35+
area = 0;
36+
}
37+
}
38+
int[] answer = new int[2];
39+
answer[0] = numberOfArea;
40+
answer[1] = maxSizeOfOneArea;
41+
return answer;
42+
}
43+
44+
public void getArea(int row, int col) {
45+
check[row][col] = true;
46+
if (row > 0 && attrPicture[row - 1][col] == attrPicture[row][col] && !check[row - 1][col]) // 상
47+
getArea(row - 1, col);
48+
if (row < attrPicture.length - 1 && attrPicture[row + 1][col] == attrPicture[row][col] && !check[row + 1][col]) // 하
49+
getArea(row + 1, col);
50+
if (col > 0 && attrPicture[row][col - 1] == attrPicture[row][col] && !check[row][col - 1]) // 좌
51+
getArea(row, col - 1);
52+
if (col < attrPicture[row].length - 1 && attrPicture[row][col + 1] == attrPicture[row][col] && !check[row][col + 1]) // 우
53+
getArea(row, col + 1);
54+
area += 1;
55+
}
56+
}

‎src/programmers/level2/week_27/Solution002.java‎

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
package programmers.level2.week_27;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* 행렬 테두리 회전하기
7+
* https://programmers.co.kr/learn/courses/30/lessons/77485?language=java
8+
*/
9+
public class Solution002 {
10+
public static void main(String[] args) {
11+
int rows = 6;
12+
int columns = 6;
13+
int[][] queries = {{2, 2, 5, 4}, {3, 3, 6, 6}, {5, 1, 6, 3}};
14+
Solution002 sol = new Solution002();
15+
System.out.println(Arrays.toString(sol.solution(rows, columns, queries)));
16+
}
17+
18+
public int[] solution(int rows, int columns, int[][] queries) {
19+
int[] answer = new int[queries.length];
20+
int[][] square = createSquare(rows, columns);
21+
22+
int idx = 0;
23+
for (int[] query : queries) {
24+
int min = 10000;
25+
int startX = query[0] - 1;
26+
int endX = query[2] - 1;
27+
int startY = query[1] - 1;
28+
int endY = query[3] - 1;
29+
int cur = square[startX][startY];
30+
int next = 0;
31+
32+
// 동
33+
for (int i = startY; i < endY; i++) {
34+
if (min > cur) min = cur;
35+
next = square[startX][i + 1];
36+
square[startX][i + 1] = cur;
37+
cur = next;
38+
}
39+
40+
// 남
41+
for (int i = startX; i < endX; i++) {
42+
if (min > cur) min = cur;
43+
next = square[i + 1][endY];
44+
square[i + 1][endY] = cur;
45+
cur = next;
46+
}
47+
48+
// 서
49+
for (int i = endY; i > startY; i--) {
50+
if (min > cur) min = cur;
51+
next = square[endX][i - 1];
52+
square[endX][i - 1] = cur;
53+
cur = next;
54+
}
55+
56+
// 북
57+
for (int i = endX; i > startX; i--) {
58+
if (min > cur) min = cur;
59+
next = square[i - 1][startY];
60+
square[i - 1][startY] = cur;
61+
cur = next;
62+
}
63+
64+
answer[idx++] = min;
65+
}
66+
67+
return answer;
68+
}
69+
70+
private int[][] createSquare(int rows, int columns) {
71+
int[][] square = new int[rows][columns];
72+
int val = 1;
73+
for (int i = 0; i < rows; i++) {
74+
for (int j = 0; j < columns; j++) {
75+
square[i][j] = val++;
76+
}
77+
}
78+
79+
return square;
80+
}
81+
}

‎src/programmers/level2/week_27/Solution003.java‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
package programmers.level2.week_27;
2+
3+
import java.util.ArrayList;
4+
import java.util.HashSet;
5+
6+
/**
7+
* 후보키
8+
* https://programmers.co.kr/learn/courses/30/lessons/42890?language=java
9+
*/
10+
public class Solution003 {
11+
ArrayList<HashSet<Integer>> candidateKey;
12+
13+
public static void main(String[] args) {
14+
String[][] relation = {{"100", "ryan", "music", "2"}, {"200", "apeach", "math", "2"}, {"300", "tube", "computer", "3"}, {"400", "con", "computer", "4"}, {"500", "muzi", "music", "3"}, {"600", "apeach", "music", "2"}};
15+
Solution003 sol = new Solution003();
16+
System.out.println(sol.solution(relation));
17+
}
18+
19+
public int solution(String[][] relation) {
20+
candidateKey = new ArrayList<>();
21+
int colSize = relation[0].length;
22+
23+
for (int i = 1; i <= colSize; ++i) {
24+
makeKeySet(-1, colSize - 1, 0, i, new HashSet<>(), relation);
25+
}
26+
27+
return candidateKey.size();
28+
}
29+
30+
private void makeKeySet(int attr, int maxAttr, int idx, int size, HashSet<Integer> keySet, String[][] relation) {
31+
if (idx == size) {
32+
for (HashSet<Integer> key : candidateKey) if (keySet.containsAll(key)) return;
33+
if (isUnique(keySet, relation)) candidateKey.add(keySet);
34+
return;
35+
}
36+
37+
for (int i = attr + 1; i <= maxAttr; ++i) {
38+
HashSet<Integer> newKeySet = new HashSet<>(keySet);
39+
newKeySet.add(i);
40+
makeKeySet(i, maxAttr, idx + 1, size, newKeySet, relation);
41+
}
42+
}
43+
44+
private boolean isUnique(HashSet<Integer> keySet, String[][] relation) {
45+
HashSet<String> set = new HashSet<>();
46+
for (String[] row : relation) {
47+
StringBuilder key = new StringBuilder();
48+
49+
for (int col : keySet) {
50+
key.append(row[col]);
51+
}
52+
53+
if (set.contains(key.toString())) return false;
54+
55+
set.add(key.toString());
56+
}
57+
return true;
58+
}
59+
}

0 commit comments

Comments
 (0)