ALGORITHM/PROGRAMMERS
[프로그래머스] 기둥과 보 설치 (2020 KAKAO BLIND RECRUITMENT)
0298
2021. 2. 11. 22:23
programmers.co.kr/learn/courses/30/lessons/60061
코딩테스트 연습 - 기둥과 보 설치
5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[
programmers.co.kr
2021-02-11
|
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
120
121
122
123
124
|
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
public class Solution60061 {
public static int N, arr[][][];
static class Robot {
int x;
int y;
int str;
public Robot(int x, int y, int str) {
this.x = x;
this.y = y;
this.str = str;
}
}
public static boolean isGidung(int x, int y) {
if(x < 0 || y < 0 || x > N || y > N || arr[x][y][0] == 0) return false;
return true;
}
public static boolean isBo(int x, int y) {
if(x < 0 || y < 0 || x > N || y > N || arr[x][y][1] == 0) return false;
return true;
}
public static boolean solveGidung(int x, int y) { // 바닥 / 또 다른 기둥 위 / 보 그 위에 / 보의 한 쪽 끝 부분
return (y == 0 || isGidung(x, y-1) || isBo(x, y) || isBo(x-1, y));
}
public static boolean solveBo(int x, int y) { // 기둥 위 / 기둥 바로 위 (x) / 기둥 끝쪽으로 / 양쪽 끝이 서로 다른 보 일 때
return (isGidung(x, y-1) || /*isGidung(x,y) || */isGidung(x+1, y-1) || (isBo(x-1, y) && isBo(x+1, y)));
}
public static int[][] solution(int n, int[][] build_frame) {
N = n+1;
arr = new int[N][N][2];
for(int i = 0; i < build_frame.length; i++) {
int x = build_frame[i][0];
int y = build_frame[i][1];
int a = build_frame[i][2];
int b = build_frame[i][3];
if(a == 0) { // 기둥
if(b == 1) { // 설치
if(solveGidung(x,y)) arr[x][y][0] = 1;
} else {
if(arr[x][y][0] == 0) continue;
arr[x][y][0] = 0;
if((isGidung(x, y+1) && !solveGidung(x, y+1)) // (1) 위에 기둥인데 기둥을 만들 수 없을 때
|| (isBo(x, y+1) && !solveBo(x, y+1)) // (2) 위에 보인데 보를 만들 수 없을 때
// || (isBo(x,y) && !solveBo(x,y)) // (3) 현재 보인데 보를 만들 수 없을 때
|| (isBo(x-1, y+1) && !solveBo(x-1, y+1)) // (3) 위의 오른쪽 보를 만들 수 없을 때
) arr[x][y][0] = 1;
}
} else { // 보
if(b == 1) {
if(solveBo(x, y)) arr[x][y][1] = 1;
} else {
if(arr[x][y][1] == 0) continue;
arr[x][y][1] = 0;
if((isGidung(x,y) && !solveGidung(x,y)) // (1) 현재 좌표에 기둥이 있는데 기둥을 만들 수 없는 경우
|| (isGidung(x+1, y) && !solveGidung(x+1, y)) // (2) 오른쪽에 기둥이 있는데 기둥을 만들 수 없는 경우
|| (isBo(x-1, y) && !solveBo(x-1, y)) // (3) 왼쪽에 보가 있는데 보를 만들 수 없는 경우
|| (isBo(x+1, y) && !solveBo(x+1, y)) // (4) 오른쪽에 보가 있는데 보를 만들 수 없는 경우
)arr[x][y][1] = 1;
}
}
}
ArrayList<Robot> list = new ArrayList<>();
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(arr[i][j][0] != 0) list.add(new Robot(i, j, 0));
if(arr[i][j][1] != 0) list.add(new Robot(i, j, 1));
}
}
int[][] answer = new int[list.size()][3];
for(int i = 0; i < list.size(); i++) {
answer[i][0] = list.get(i).x;
answer[i][1] = list.get(i).y;
answer[i][2] = list.get(i).str;
}
return answer;
}
public static void main(String[] args) {
// int b[][] = {
// {1,0,0,1},
// {1,1,1,1},
// {2,1,0,1},
// {2,2,1,1},
// {5,0,0,1},
// {5,1,0,1},
// {4,2,1,1},
// {3,2,1,1}
// };
int b[][] = {
{0,0,0,1},
{2,0,0,1},
{4,0,0,1},
{0,1,1,1},
{1,1,1,1},
{2,1,1,1},
{3,1,1,1},
{2,0,0,0},
{1,1,1,0},
{2,2,0,1}
};
int r[][] = solution(5, b);
for(int p[]: r) System.out.println(Arrays.toString(p));
}
}
|
cs |
#문제풀이
몇 주 동안 조금씩 계속 봤던 문제이다.
필요없는 조건을 넣어서 계속 틀렸었다... 한 달 뒤쯤 다시 풀어봐야할 것 같다.