티스토리 뷰
https://programmers.co.kr/learn/courses/30/lessons/60061#
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
|
graph = None
def is_possible(x, y):
if graph[x][y] == 1: # 기둥
# 바닥이거나 // 보의 오른쪽 끝 부분 위에 있거나(왼쪽 끝에 있으면 같은 위치이므로 3) // 다른 기둥 위거나
if y == 0 or (x > 0 and graph[x - 1][y] >= 2) or graph[x][y - 1] in (1, 3):
return True
else:
return False
elif graph[x][y] == 2: # 보
# 한쪽 끝 부분이 기둥 위에 있거나 // 양쪽 끝 부분이 다른 보와 동시에 연결
if graph[x][y - 1] in (1, 3) or graph[x + 1][y - 1] in (1, 3) \
or (x > 0 and graph[x - 1][y] >= 2 and graph[x + 1][y] >= 2):
return True
else:
return False
else: # 기둥과 보 함께 설치
# 다른 기둥 위거나 // 양쪽 끝 부분이 다른 보와 동시에 연결되거나 // 오른쪽 기둥 위거나
if graph[x][y - 1] in (1, 3) or (x > 0 and graph[x - 1][y] >= 2 and graph[x + 1][y] >= 2) \
or graph[x + 1][y - 1] in (1, 3):
return True
else:
return False
def solution(n, build_frame):
global graph
graph = [[0] * (n + 1) for _ in range(n + 1)]
for frame in build_frame:
x, y, a, b = frame
now = graph[x][y]
a += 1
if b == 0:
graph[x][y] -= a
else:
graph[x][y] += a
for i in range(n + 1):
flag = False
for j in range(n + 1):
if graph[i][j] != 0 and not is_possible(i, j):
flag = True
graph[x][y] = now
break
if flag:
break
answer = list()
for i in range(n + 1):
for j in range(n + 1):
if graph[i][j] == 1:
answer.append([i, j, 0])
elif graph[i][j] == 2:
answer.append([i, j, 1])
elif graph[i][j] == 3:
answer.append([i, j, 0])
answer.append([i, j, 1])
return answer
|
cs |
카카오 구현 문제는 정말 까다로운 것 같다..
이번 문제도 구현문제라서 문제에서 설명해주는대로 풀면 되지만, 꽤나 고생했다.
내가 구현한 코드에서 중요한 부분은, 첫째로 문제에서와 다르게 기둥을 1, 보를 2로 둔 것이다.
격자에 구조물을 표시해야 하는데, 기둥을 0으로 하면 더해도 표시가 안나기 때문이다. 기둥과 보가 같은 좌표에 있으면 더해서 3을 표시한다.
둘째로, 구조물 리스트(다른 언어에서는 벡터나 배열로 주어질 것)에서 새로운 구조물을 가져오면서 계속 이를 적용하고, 모든 구조물에 대해 조건을 만족하는지 확인한 것이다. 지우거나 추가하는 부분에 연결된 부분만 검사하면, 연쇄적으로 문제가 생기는 부분을 잡지 못할 수 있다. n이 최대 100, 구조물의 갯수가 최대 1000개이니 최대치로 검사해도 100000번이다. 그냥 완전탐색을 유도한 것 같다.
셋째로, 문제의 매개변수 조건을 잘 읽어서, 쓸데없는 조건을 넣지 않은 것이다. 문제를 잘 보면, 보는 바닥에 깔리지 않고, 벽면을 벗어나는 구조물은 없다. 그런 조건까지 없었으면 코드가 진짜 우주로 갔을 것 같다.
카카오 공채 문제는 진짜 보면 볼수록 잘 만든 것 같다는 생각을 하게 된다.
'algorithm'''problem solve' 카테고리의 다른 글
[프로그래머스] 외벽 점검 (카카오, 구현, 순열) (0) | 2020.10.02 |
---|---|
[백준] 15686 - 치킨 배달 (구현, 브루트포스) (0) | 2020.10.02 |
[백준] 3190 - 뱀 (구현, Deque) (0) | 2020.09.30 |
[프로그래머스] 자물쇠와 열쇠 (2020 카카오 공채, 완전탐색) (0) | 2020.09.30 |
[프로그래머스] 문자열 압축 (0) | 2020.09.28 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 백트래킹
- c++
- 오픈소스
- 브루트포스
- 이분탐색
- 완전탐색
- 정렬
- webOS
- LG
- DFS
- 동적 계획법
- BaekJoon
- 카카오
- 인공지능
- 한화큐셀
- DP
- 알고리즘
- 코딩
- 플로이드 와셜
- 피보나치
- 파이썬
- 1932
- Dynamic Programming
- 백준
- BFS
- PyPy3
- 구현
- c
- 컨트리뷰톤
- 프로그래머스
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함