두 번째 알고리즘 시험을 보는 날이 되었다. 아무리 생각해도 알고리즘을 공부하는 것은 쉬운 일이 아닌 것 같다. 그래도 포기하지 않고 꾸준히 공부하다보면 이전보다는 훨씬 발전된 모습을 발견할 수 있을 것이라고 믿고 할 수 있는 만큼은 해보려고 한다.
문제에서 구하는 것
이 문제에서는 "바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다." 라고 함.
즉, 인형을 뽑아 바구니에 저장해두는데, 이 때 같은 게 2개 쌓은 인형 두 개가 없어지게 됨. 따라서, 뽑은 순서대로 저장해 놓는 자료구조가 필요하고 순서대로 데이터를 저장하는 자료구조는 "스택" 또는 "큐"임. 현재 바구니는 아래서부터 쌓이고 위에서 빠지는 형태이므로 스택을 써야 한다는 것을 유추할 수 있음.
▶ 우선 반환해 줘야 하는 것: "크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수"
따라서 answer = 0 을 지정해서 반환해 줌. 그리고 스택을 이용해서 바구니를 구현할 것이라고 했기 때문에 그 값을 저장해두기 위한 bucket = [] 라는 변수를 만들어 둘 것.
def solution(board, moves):
bucket = []
answer = 0
return answer그러면 이제 moves 에 따라서 board 의 특정 칼럼의 가장 윗값을 조회해서 bucket 안에 넣어줘야 하는데 이는 moves 가 1일 때 board 의 1열을 (실제로는 인덱스 0) 위에서부터 조회해서 빈 값이 아닐 때 bucket 에다 쌓고, 또 moves 가 5라고 한다면 board 의 5열을 (실제로는 인덱스 4) 위에서부터 조회해서 빈 값이 아닐 때 bucket 에다 쌓는다는 것.
python
# 아래와 같은 board 에 [1,5,3,5,1,2,1,4] 라는 moves 가 입력된다고 해볼 것.
# 0. moves 에서 원소를 하나씩 꺼내면서 board 의 열에 해당하는 가장 위의 원소를 bucket 에 넣으면 됨.
[
[0, 0, 0, 0, 0],
[0, 0, **1**, 0, **3**],
[0, **2**, 5, 0, 1],
[**4**, 2, 4, **4**, 2],
[3, 5, 1, 3, 1]
] # board
# 1. 첫 번째 원소인 1, 즉 0번째 인덱스의 칼럼인 [0,0,0,4,3] 에서 가장 위의 원소인 4를 꺼내 bucket 에 넣음.
[
[0, 0, 0, 0, 0],
[0, 0, 1, 0, 3],
[0, 2, 5, 0, 1],
[**4**, 2, 4, 4, 2],
[3, 5, 1, 3, 1]
] # board
->
[
[0, 0, 0, 0, 0],
[0, 0, 1, 0, 3],
[0, 2, 5, 0, 1],
[**0**, 2, 4, 4, 2],
[3, 5, 1, 3, 1]
] # board
[4] # bucket
# 2. 다음 원소인 5, 즉 4번째 인덱스의 칼럼인 [0,3,1,2,1] 에서 가장 위의 원소인 3을 꺼내 bucket 에 넣음.
[
[0, 0, 0, 0, 0],
[0, 0, 1, 0, **3**],
[0, 2, 5, 0, 1],
[0, 2, 4, 4, 2],
[3, 5, 1, 3, 1]
] # board
->
[
[0, 0, 0, 0, 0],
[0, 0, 1, 0, **0**],
[0, 2, 5, 0, 1],
[0, 2, 4, 4, 2],
[3, 5, 1, 3, 1]
]# board
[3, 4] # bucket
# 3. 다음 원소인 3, 즉 2번째 인덱스의 칼럼인 [0,1,5,4,1] 에서 가장 위의 원소인 1을 꺼내 bucket 에 넣음.
[
[0, 0, 0, 0, 0],
[0, 0, **1**, 0, 0],
[0, 2, 5, 0, 1],
[0, 2, 4, 4, 2],
[3, 5, 1, 3, 1]
]# board
->
[
[0, 0, 0, 0, 0],
[0, 0, **0**, 0, 0],
[0, 2, 5, 0, 1],
[0, 2, 4, 4, 2],
[3, 5, 1, 3, 1]
]# board
[1, 3, 4] # bucket
# 4. 다음 원소인 5, 즉 4번째 인덱스의 칼럼인 [0,0,1,2,1] 에서 가장 위의 원소인 1을 꺼내 bucket 에 넣음.
# 이 때, bucket의 맨 위에 1이 있습니다. 그러면 동일한 1, 1은 제거되고 result 에 2가 추가됨.
[
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 2, 5, 0, **1**],
[0, 2, 4, 4, 2],
[3, 5, 1, 3, 1]
]# board
->
[
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 2, 5, 0, **0**],
[0, 2, 4, 4, 2],
[3, 5, 1, 3, 1]
]# board
[3, 4] # bucket위의 내용을 코드로 구현하려고 할 때, 먼저 moves 를 반복문을 통해서 조회함. 여기서 move 를 인덱스로 변환해주기 위해서 index 라는 변수에 move - 1 값을 저장함. 이후 어떤 인덱스를 구해야 하는지는 알게될 때, 이 정보를 바탕으로 board 를 조회해야 함. 따라서 board 의 row 값들을 row_info 에 담은 뒤, 각 행에서 해당 index 에 있는 열의 원소 값이 0인지 아닌지 확인함. 만약 0이 아니라면 bucket 에 append 해서 넣어주고 중단시키면 됨.
def solution(board, moves):
bucket = []
answer = 0
for move in moves:
index = move - 1
for row_info in board:
if row_info[index] != 0:
bucket.append(row_info[index])
break
return answer하지만 이렇게 계속 bucket 에 넣으면 안 됨. 해당 row_info[index] 값을 bucket 에 담았다는 것은, 해당 원소의 값을 뽑았다는 것을 의미하므로 0으로 초기화 시켜주는 작업을 해야 함. 그래야 맨 위의 인형이 뽑혀져 나갔다는 것을 드러내줄 수 있음.
def solution(board, moves):
bucket = []
answer = 0
for move in moves:
index = move - 1
for row_info in board:
if row_info[index] != 0:
bucket.append(row_info[index])
row_info[index] = 0
break
return answer또한, 추가적인 로직이 하나 더 필요함. 맨 위의 인형과 방금 넣은 인형이 같다면, 그 두 인형을 제거하고 answer 에 2를 추가하는 로직이 필요함.
따라서 bucket 의 맨 뒤에 원소가 맨 뒤에서 두번째 원소와 같다면, bucket 의 두 원소를 제거하며 answer 를 2를 더해주는 로직을 추가하면 됨.
def solution(board, moves):
bucket = []
answer = 0
for move in moves:
index = move - 1
for row_info in board:
if row_info[index] != 0:
bucket.append(row_info[index])
row_info[index] = 0
if len(bucket) >= 2 and bucket[-1] == bucket[-2]:
answer += 2
bucket = bucket[0:-2]
break
return answer실제 코드를 작성하기 전에, 요구사항에 대해서 먼저 분석하고 어떻게 해결할 것인지에 대해서 입력 예시를 통해 생각해보시는 것이 좋음. 실제 런타임 시에 변수들이 어떻게 변화되는지에 대해 생각하다보면 "아 이렇게 하면 더 효율적이겠구나" 라는 직관이 오게 되고 이런 단계가 올 때까지 연습해보는 게 좋음.
# 결과 코드
def solution(board, moves):
bucket = []
answer = 0
for move in moves:
index = move - 1
for row_info in board:
if row_info[index] != 0:
bucket.append(row_info[index])
row_info[index] = 0
if len(bucket) >= 2 and bucket[-1] == bucket[-2]:
answer += 2
bucket = bucket[0:-2]
break
return answer