출처
: Programmers
문제
정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.
n행n열 크기의 비어있는 2차원 배열을 만듭니다.- i = 1, 2, 3, …, n에 대해서, 다음 과정을 반복합니다. 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
- 1행, 2행, …,
n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다. - 새로운 1차원 배열을
arr이라 할 때,arr[left],arr[left+1], …,arr[right]만 남기고 나머지는 지웁니다. 정수n,left,right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤
n≤ $10^7$ - 0 ≤
left≤right< $n^2$ right-left< $10^5$
(생략)
나의 풀이(시도)
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
from collections import deque
def solution(maps):
n_size = len(maps)
m_size = len(maps[0])
visited = [[False for _ in range(m_size)]
for __ in range(n_size)]
start = (0, 0)
result = bfs(maps, start, visited)
if result == 1:
answer = -1
else:
answer = result
return answer
def bfs(graph, start, visited):
'''
# graph : 2차원 배열
# start = (y, x) = (col, row)
# visited : 2차원 배열
'''
# 큐(Queue) 구현 위해 deque 라이브러리 사용
queue = deque()
queue.append(start)
col = start[1]
row = start[0]
# 현재 Node 방문 처리
visited[col][row] = True
n_size = len(graph)
m_size = len(graph[0])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# Queue 빌 때까지 반복
while queue:
# Queue에서 원소 하나 뽑기
y, x = queue.popleft()
for i in range(4):
ny = y + dx[i]
nx = x + dy[i]
if (nx < 0 or nx >= m_size
or ny < 0 or ny >= n_size):
continue
if graph[ny][nx] == 0:
continue
if (graph[ny][nx] != 1 and
visited[ny][nx] == True):
continue
if graph[ny][nx] == 1:
graph[ny][nx] = graph[y][x] + 1
visited[ny][nx] = True
queue.append((ny, nx))
return graph[n_size - 1][m_size - 1]
이코테(나동빈)의 DFS/BFS를 참고해서
이번 기회에 두 탐색의 컨셉과 구체적 코드를 학습했다.
그리고 이 문제에서는
그런 BFS 코드를 바탕으로 문제 조건에 맞게 바꿨다.
마침, 문제도 $(0, 0)$에서 $(n-1, m-1)$로 가는 것이
전제로 되어있어서 딱 적용하기 좋았던 것 같다.
사실, 당황했던 부분도 있었다.
1
2
n_size = len(maps)
m_size = len(maps[0])
이런 부분은 처음부터 고려하지 않았고,
단지 정사각형인 걸로 생각해버렸는데,
이걸 수정하니까 직사각형인 경우도 다 통과가 떴다.
그리고,
1
2
3
if (graph[ny][nx] != 1 and
visited[ny][nx] == True):
continue
혹시나 해서 이걸 넣었는데
딱히 도움은 안 된 것 같다.
데이터가 아주 클 때는 의미가 있을까?
다른 사람들의 풀이
1
2
3
4
5
6
7
class ALWAYS_CORRECT(object):
def __eq__(self,other):
return True
def solution(a):
answer = ALWAYS_CORRECT()
return answer;
(출처: 프로그래머스 스쿨 다른사람 풀이)
??????? ㅋㅋㅋㅋㅋㅋㅋ
이거 보고 좀 현웃 터졌다…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(maps):
stack = [(0,0, 1)]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
while stack:
x, y, d= stack.pop(0)
for q in range(4):
ny = y + dy[q]
nx = x + dx[q]
if ny <0 or nx <0 or ny >= len(maps) or nx >= len(maps[0]):
continue
else:
if maps[ny][nx] ==1 or maps[ny][nx] > d+1:
maps[ny][nx] =d+1
if ny == len(maps) -1 and nx == len(maps[0])-1:
return d+1
stack.append((nx, ny, d+1))
return -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
from collections import deque
def solution(maps):
x_move = [1, 0, -1, 0]
y_move = [0, 1, 0, -1]
x_h, y_h = (len(maps[0]), len(maps))
queue = deque([(0, 0, 1)])
while queue:
x, y, d = queue.popleft()
for i in range(4):
nx = x + x_move[i]
ny = y + y_move[i]
if nx > -1 and ny > -1 and nx < x_h and ny < y_h:
if maps[ny][nx] == 1 or maps[ny][nx] > d + 1:
maps[ny][nx] = d + 1
if nx == x_h - 1 and ny == y_h - 1:
return d + 1
queue.append((nx, ny, d + 1))
return -1
(출처: 프로그래머스 스쿨 다른사람 풀이)