출처
: Programmers
문제
크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)
게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.
[제한사항]
- board 배열은 2차원 배열로 크기는 “5 x 5” 이상 “30 x 30” 이하입니다.
- board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
- 0은 빈 칸을 나타냅니다.
- 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
- moves 배열의 크기는 1 이상 1,000 이하입니다.
- moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.
나의 풀이(시도)
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
import numpy as np
'''
같은 것 2개를 없앰
res_cnt: 누적된 값 그대로 받음
'''
import numpy as np
'''
처음으로 nonzero인 idx
(이걸 구해놔야
리스트 참조 횟수 줄임)
'''
def first_nonzero_idx(board):
size = len(board)
first_nz_idxs = \
[next((i for i, x in enumerate(board[j]) if x), None) for j in range(size)]
return first_nz_idxs
def solution(board, moves):
board = np.transpose(board).tolist()
# 쌓기 위한 리스트
stack_list = []
first_nz_idxs = first_nonzero_idx(board)
res_cnt = 0
for _ in moves:
# (one move의 값) - 1로 인덱스!!!
pick_idx = _ - 1
first_nz_pos = first_nz_idxs[pick_idx]
# 아무것도 없는 column엔
# 뽑을 것 없으므로
if (first_nz_pos == len(board)):
continue
temp_pick = board[pick_idx][first_nz_pos]
stack_list.append(temp_pick)
# pop을 했으므로 0으로 설정
board[pick_idx][first_nz_pos] = 0
# 빠지게 되면
# 0이 늘어나므로 인덱스도 1 추가
first_nz_idxs[pick_idx] += 1
stack_size = len(stack_list)
if (stack_size == 1 or stack_size == 0):
continue
elif (stack_size == 2 and (stack_list[0] != stack_list[1])):
continue
else:
if (stack_list[stack_size - 1] == stack_list[stack_size - 2]):
stack_list.pop()
stack_list.pop()
res_cnt += 2
answer = res_cnt
return answer
이 문제는
약 절반의 테스트 케이스 실패로 풀지 못했다.
아마도 실패인 케이스들은 큰 데이터인 것 같다.
즉, 런타임 에러였는데,
그걸 줄일려고 계속 고민하면서 수정했지만
결국에는 해결하지 못했다.
일단 이렇게 작성한 이유는 이러하다.
np.transpose(board).tolist()는
문제에서 주어진 데이터 형식을 다루기 쉽게 하려면
전치행렬로 바꿔야 할 것 같다고 생각해서였다.
그리고 .tolist()를 써야만 리스트 연산이 된다.
first_nonzero_idx()는
원래는 아래의 코드로 짰었다.
1
2
3
4
5
6
7
8
9
def first_nonzero_idx(board):
first_nz_idxs = [-1, -1, -1, -1, -1]
size = len(board)
for i in range(size):
for j in range(size):
if (board[i][j] != 0):
first_nz_idxs[i] = j
break
return first_nz_idxs
일단,
처음으로 0이 아닌 값의 인덱스를 저장하기 위해서다.
먼저 이렇게 해놓으면
나중에 반복문에서 위쪽 0인 값들을 제끼고
바로 접근할 수 있다고 생각했기 때문이다.
그러나
위의 코드는 시간복잡도가 $O(N^2)$이다.
만약 인형이 1개만 있는 큰 데이터라면
시간 초과가 날 수밖에 없다.
그래서 검색을 해보다가
스택오버플로우의 한 게시글을 보고
이렇게 바꾸었다.
1
2
3
4
5
def first_nonzero_idx(board):
size = len(board)
first_nz_idxs = \
[next((i for i, x in enumerate(board[j]) if x), None) for j in range(size)]
return first_nz_idxs
왜 수학, 그리고 알고리즘을 생각해야하는지
뼈저리게 느낄 수 있는 부분이었다…
그리고
picking()과 sames_pop()이
각각 인형 뽑기, 같은 인형 pop하는 역할이다.
그런데 여기서 내가 잘못 생각한 것 같다.
당연히 스택Stack 개념은 염두에 뒀으나
그걸 완전히 생각하진 못한 것 같다.
자꾸 같은 것 2개만 없앤다는 생각에
리스트의 remove() 메서드를 썼기 때문이다.
이렇게 쓰면서 생각을 해보니까
sames_pop()에서 굳이 while을 왜 썼는지 싶다.
다른 사람들의 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solution(board, moves):
stacklist = []
answer = 0
for i in moves:
for j in range(len(board)):
if board[j][i-1] != 0:
stacklist.append(board[j][i-1])
board[j][i-1] = 0
if len(stacklist) > 1:
if stacklist[-1] == stacklist[-2]:
stacklist.pop(-1)
stacklist.pop(-1)
answer += 2
break
return answer
(출처: 프로그래머스 스쿨 다른사람 풀이)
정말 아름답다…
더군다나 리스트를 변환조차 하지 않았다.
저렇게 인덱스 참조를 할 수 있구나를 깨달았다…